boj 11501 : Stock(주식)

boj 11501 : Stock(주식)

https://www.acmicpc.net/problem/11501

언뜻 간단해보이지만 아이디어를 떠올리기가 쉽지만은 않은 문제이다.

a[i]를 i번째 주식의 가격이라 할 때, i번째를 산다면 얼마에 팔 수 있는가?

term_max를 팔게될 가격이라고 한다면,

1. term_max = max(a[k]) {k = i~n}

그렇다면 이득은 얼마인가? 

2. i번째 얻는 이득 : term_max - a[i];

위 알고리즘의 시간복잡도는 n이다.