설명한 대로라면 이런 TC에서는 올바른 답을 내지 못할 거 같네요.

답은 15일까요? 39일까요?

제가 아직 구현은 안해봤지만 

주식이 떨어지는 시점에 모두 파는 알고리즘은 틀린 것 같습니다

예를 들어  2 2 1 3  이면

2 2 1 을 구입하고 3에서 팔아야 최대이익이 납니다

이론상으로는 최댓값일때까지 산다음 팔고

다시 나머지중 최댓값일때까지 산다음 팔고해야 될 거 같은데

n이 백만까지라 최댓값을 계속해서 찾는 시간이 너무 오래걸리는군요..

O(n^2) 시간이 걸립니다

그런데 어차피 최댓값을 찾아도 그 뒤에 나오는 주식들은 최댓값이 몇이든간에

다시 처음부터 사고팔고를 해야되니까 결국에는 뒤에 나오는 최댓값에 따라서 또 최대이익이 결정되겠지요

따라서 뒤에서 부터 하나씩 빼가면서 탐색을하게되면

값이 커지는 시점은 뒤의 최댓값이 갱신되는 때이고

값이 작아지는 시점은 그때마다 최댓값 - a[i]를 최대이익에 합해주면 됩니다

....1 2 3 4 2 1 1

이런 경우 

맨 처음 최댓값을 1로 갱신

그 다음 탐색에서 1을 발견. 같은 경우는 사고팔고 의미가 없으므로

그 다음 탐색으로 넘어가서 2를 발견 최댓값을 2로 갱신

그 다음 탐색에서 4를 발견 최댓값을 4로 갱신

이후 3 2 1 은 계속 작아지므로

그 말인즉슨 4보다 작으니까 계속 사뒀다가 4에서 파는게 이익이라는 뜻이므로

최대이익+=(4-3)+(4-2)+(4-1)

따라서 총 최대이익은 6

이 방식으로 하면 O(n)에 해결할 수 있을 겁니다

문제를 정확히 이해하지 못하여 아래 중 잘못된 접근 방식으로 알고리즘 로직을 짰습니다.

- 잘못된 접근: 주가가 떨어지는 시점에 기존 구입했던 주식 판매 (Greedy)

- 올바른 접근: 주가가 떨어지는 시점이 아니라, 현재 주가를 현재일 이후에 가장 비싸게 팔 수 있는 날에 판매

문제 설명에 도움주신 alphago92  chogahui05 감사합니다. 덕분에 문제 해결하였습니다.

와 뒤에서부터 체크할 생각은 못했는데..

alphago92 님 대박ㅠㅠ

뒤에서 부터 하는 풀이 넘 멋있네욤