【Leetcode】121. Best Time to Buy and Sell Stock

Description

Say you have an array for which the ith element is the price of a given stock on day i.

If you were only permitted to complete at most one transaction (ie, buy one and sell one share of the stock), design an algorithm to find the maximum profit.

Example 1:
Input: [7, 1, 5, 3, 6, 4]
Output: 5
max. difference = 6-1 = 5 (not 7-1 = 6, as selling price needs to be larger than buying price)

Example 2:
Input: [7, 6, 4, 3, 1]
Output: 0

In this case, no transaction is done, i.e. max profit = 0.

Solution

public int maxProfit(int[] nums) {
        int max = 0;
        if (nums.length <= 1) {
            return 0;
        }
        for (int i = nums.length - 1; i >= 0; i--) {
            for (int j = i - 1; j >= 0; j--) {
                max = Math.max(nums[i] - nums[j], max);
            }
        }
        return max;
    }

Result

TLE

Analyse

确实是手生了，这个题没有秒出思路，看来代码能力退化的很快。

Optimization

First

public int maxProfit(int[] nums) {
        if (nums.length <= 1) {
            return 0;
        }
        int minSoFar = nums[0];
        int max = 0;
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] < minSoFar) {
                minSoFar = nums[i];
            } else {
                max = Math.max(max, nums[i] - minSoFar);
            }
        }
        return max;
    }

Second

public int maxProfit(int[] nums) {
        if (nums.length <= 1) {
            return 0;
        }
        int maxCur = 0;
        int maxSoFar = 0;
        for (int i = 1; i < nums.length; i++) {
            maxCur = Math.max(0, maxCur += nums[i] - nums[i - 1]);
            maxSoFar = Math.max(maxCur, maxSoFar);
        }
        return maxSoFar;
    }

Analyse

这个题的思路其实很简单，就是最长连续子串的思路。第一种方法，保持住每次的最小值，然后将最小值和当前值比，得出的结果一直在更新，O(n)就可以完成第二种方法稍微取巧，新建了一个maxSoFar值，而每次都是比0和与当前差值的和的比较，如果是当前差值的和为负数，可能目前maxCur会减小，但是maxSoFar不会减小，而后面再累加的话就可能会因为后面有累加的值而增加，之所以需要累加，是因为他们开始每次算的都是相邻的差值和如何，但是maxSoFar每次都在更新，这里和0比较大小也很重要，因为如果小于0的话，前面其实可以丢弃了，再看后面单独加起来能不能超越maxSoFar。