[백준 25644번] 최대 상승 (C++)

문제링크 : https://www.acmicpc.net/problem/25644

#include <bits/stdc++.h> 
using namespace std;
#define fastio ios_base::sync_with_stdio(0); cin.tie(0);
int n, result = 0, sum = 0;
vector<int> arr;

int main()
{
	fastio;
	cin >> n;
	for(int i=0; i<n; i++)
	{
		int a;
		cin >> a;
		arr.push_back(a);  //a1 ~ an 푸쉬
	}

	for (int i = arr.size() - 1; i >= 0; i--)
	{
		result = max(result, arr[i]);     //최댓값 저장
		sum = max(sum, result - arr[i]);  //최댓값과 현재 값의 차이 중 가장 큰 값을 저장
	}

	cout << sum;
	
}

처음에 이중 for문으로 하니 시간초과가 났다.

배열의 마지막부터 탐색하여 최댓값을 따로 저장해나가고,

최댓값과 현재값의 차이가 가장 큰 값을 또 따로 저장하여 출력한다.