[백준 11501] 주식

www.acmicpc.net/problem/11501

11501번: 주식

그리디 알고리즘을 사용한다.

문제 예시에서도 잠깐 비춰지지만 수열 전체가 오름차순이면 사서 파는게 이득이고 수열 전체가 내림차순이면 존버가 이득이다.

 

수열 전체가 내림차순인지 오름차순인지 앞에서 부터 순열을 돌아선 알 수 없다. 따라서 맨 뒤부터 숫자를 확인한다.

 

순열이 오름차순일수도 내림차순일수도 오르락 내리락 할수도 있다. 아마 대부분 오르락 내리락 할 것이다.

그렇다면 뒤에서 숫자를 확인하며 최댓값과 비교한다.

만약 최댓값보다 큰 수가 등장한다면 최댓값을 갱신한다.

최댓값보다 작은 숫자가 등장한다면그 차를 더한다.

#include <stdio.h>
#include <vector>

using namespace std;
int t, n;
int arr[1000000];
long long ans;
long long m;
int main(void)
{
  scanf("%d", &t);
  while (t--)
  {
    scanf("%d", &n);
    for (int i = 0; i < n; i++)
    {
      scanf("%d", &arr[i]);
    }

    m = -1;
    ans = 0;
    for (int i = n - 1; i > -1; i--)
    {
      if (m < arr[i])
      {
        m = arr[i];
      }
      else
      {
        ans += (m - arr[i]);
      }
    }

    printf("%lld\n", ans);
  }

  return 0;
}