HackerRank# Stock Maximize

원제 주소
 
왜 다이내믹 플랜으로 하는지 모르겠어요 몇 번 스캔하면 되잖아요
해커랭크의 제목은 롱롱 장르를 특히 좋아하는데, 안 쓰면 터져.
 
코드:

 1 #include <cmath>

 2 #include <cstdio>

 3 #include <vector>

 4 #include <iostream>

 5 #include <algorithm>

 6 using namespace std;

 7 

 8 #define MAX_N 50008

 9 

10 long long share[MAX_N];

11 bool sell[MAX_N];

12 

13 int main() {

14     /* Enter your code here. Read input from STDIN. Print output to STDOUT */   

15     int T, N;

16     cin >> T;

17     while (T--) {

18         long long max_share = 0;

19         long long profit = 0;

20         long long cnt = 0;

21         cin >> N;

22         for (int i = 0; i < N; i++)

23             cin >> share[i];

24         max_share = share[N - 1];

25         for (int i = N - 1; i >= 0; i--) {

26             sell[i] = share[i] >= max_share;

27             max_share = max(max_share, share[i]);

28         }

29         for (int i = 0; i < N; i++) {

30             if (sell[i]) {

31                 profit += cnt * share[i];

32                 cnt = 0;

33             } else {

34                 profit -= share[i];

35                 cnt += 1;

36             }

37         }

38         cout << profit << endl;

39     }

40     return 0;

41 }