121.Buy And Sell Stock

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:

1
2
3
4

Input: prices = [7,1,5,3,6,4]
Output: 5
Explanation: Buy on day 2 (price = 1) and sell on day 5 (price = 6), profit = 6-1 = 5.
Note that buying on day 2 and selling on day 1 is not allowed because you must buy before you sell.

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:

Buy: price[i] = min{prices[:i]}

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

Solution:

1.Keep track of the minimun price so far:

1
2
3
4
5
6
7
8
9

Traverse the price:

​	L = the Lowest price up to day i
	P = the max profit up to day i
	
	L.update
	P.update

//Buy at the lowest price, sell at day i.

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).

Using Kadane’s Algorithm

1
2
3
4
5
6
7
8
9
10

class Solution:
    def maxSubArray(self, nums):
        # Kadane's Algorithm
        maxCurrent = maxGlobal = nums[0]
        for i in range(1, len(nums)):
            # the maxCurrent is sum(maxCurrent+num)(the max subarray before this elem) or num
            maxCurrent = max(nums[i], maxCurrent + nums[i])
            # update maxGlobal = max(maxCurrent)
            maxGlobal = max(maxCurrent, maxGlobal)
        return maxGlobal