Description:

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.

Example 1:

Brute Force:

Traverse all price pairs, ans = max(ans,pair[j]-pair[i]), where j > i.

Steps:$n^2/2$ -> TLE

Note:

Define:

Max_profit = max{price[j]-price[i]}

0<= i < j < n-1

Finding:

Sell: price[j] = max{prices[j:]}

Solution:

2.Convert the priceList to the gainList

Example:

prices = [7,1,5,3,6,4]

Gains = [0,-6,4,-2,3,-2]

Note:

The profit is the sum of a subarray in gains.

And the max_profit = the largest sum of subarray of an array(LeetCode 53).