[Array] Best Time to Buy and Sell Stock

You are given an array prices where prices[i] is the price of a given stock on the ith day.

You want to maximize your profit by choosing a single day to buy one stock and choosing a different day in the future to sell that stock.

Return the maximum profit you can achieve from this transaction. If you cannot achieve any profit, return 0.

 

 

가격과 각 index가 날짜인 배열이 주어져 있을때

내가 어느 날짜에 사서 어느 날짜에 팔아야 최대 이익인가를 판단하는 문제

즉, 최대 index와 최소 index를 찾아 차이를 리턴하고, 최대 index가 최소 index보다 앞서면 0을 리턴하는 문제이다

 

이런 문제의 함정은 역시 시간복잡도에 있다

단순히 생각해보면 for를 두 번 돌면 되겠거니 생각이 들기 때문이다.

 

이 문제는 그나마 간단했다.

최솟값이 정해지면 그 앞의 원소들은 점검할 필요가 없었기 때문이다.