[백준] 11501번: 주식

-문제: https://www.acmicpc.net/problem/11501

11501번: 주식

 

-틀린 풀이:

리스트에서 최댓값을 구한 후 인덱스를 진행하다가 인덱스와 인덱스 값이 모두 크면 최댓값-인덱스값을 저장하는 식으로 진행했더니 시간초과가 발생했다. 

매 반복마다 최댓값을 구하려고한 이유는 예제3번에서처럼 가격 3 이후로 최댓값은 2이므로, 그것을 기준으로 계산해야 답이 4가 아닌 5가 나왔기 때문이다. 여기서 시간초과가 발생한 것 같다(매번 리스트에서 최댓값을 조회하는 것 때문)

 

-정답풀이:

이전에 풀었던 문제들과 비슷하게 리스트 끝 값을 기준으로 진행하면 성공한다

왼쪽부터 시작했을 때 증가폭이 오르락 내리락하면 리스트 오른쪽부터 진행해보는 걸 시도해보자