[백준] #11501 주식

문제

기존에 생각한 알고리즘은 최댓값일때까지 산다음 팔고 나머지중 최댓값일때까지 산다음 팔고 를 반복하는 알고리즘이었다. 그런데 뭐가 잘못됐는지 자꾸 틀렸습니다가 나와서 반례도 찾을 겸 질문검색에 있는 글들을 읽어봤다. 그런데 뒤에서부터 확인하면 된다는 좋은 아이디어를 알려주신 분이 계셔서 그렇게 풀었다.

#include<iostream>

using namespace std;

int arr[1000000];
int main(){
    int t,n;
    int max_v=0;
    long long ans=0;

    ios_base::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
   

    cin>>t;
    for(int i=0;i<t;i++){
        cin>>n;
       max_v=0;
        ans=0;
        for(int j=0;j<n;j++){
            cin>>arr[j];
            
            
        }

        for(int j=n-1;j>=0;j--){
            max_v=max(max_v,arr[j]);
            if(max_v<=arr[j]){
                max_v=arr[j];
                continue;
            }

            else{
                ans+=max_v-arr[j];

            }
        }
        cout<<ans<<"\n";

        
    }
}