BestTimeToBuyAndSellStock [source code]

public class BestTimeToBuyAndSellStock {
static

public class Solution {
    public int maxProfit(int[] prices) {
        int n = prices.length;
        if (n == 0) return 0;
        int[] mins = new int[n];
        mins[0] = prices[0];
        for (int i = 1; i < n; i++) mins[i] = (prices[i] < mins[i - 1]) ? prices[i] : mins[i - 1];
        int res = 0;
        for (int i = 1; i < prices.length; i++) {
            res = Math.max(res, prices[i] - mins[i - 1]);
        }
        return res;
    }
}

    public static void main(String[] args) {
        BestTimeToBuyAndSellStock.Solution tester = new BestTimeToBuyAndSellStock.Solution();
    }
}

这个题目还算不错的一次 AC, 虽然速度不怎么样, 只有3(13), 不过一次就直接作对还是很开心的.

尽管如此, 这个题目刚开始写的时候还是费了不少想头. 这个题目能够想到 DP 不算是很难, 然后你想到 DP 按照我们之前的总结, 你就要从两个角度来思考:

1. declaratively: find a value that satisfies the DP property ;
2. imperatively: how many indices should you choose for memo table? and what are they?

好在这个问题不算特别复杂, 从第二点来看, 首先长度肯定是一个 index, 但是我们是否需要第二个index 呢? 刚开始我以为是需要的, 因为这一题的 DP Property, 也就是怎么从 subsolution (n-1的 solution) 得到 bigger solution(n 的 solution), 一开始并不是非常明显.
不过后来想通了就发现这个题目其实一个 index 就够了.

至于具体的思路还是很清晰的, 就是两个 DP 的过程, 两个都是用 bottom-up 来写, 都是O(n), 然后第二个 DP 不维护一个 table, 直接一个 res 就足够了. 虽然这个对于整体的 space 并没有改善, 因为第一个 DP 的 mins 已经占用了O(n) 的 space.

下面这个是 submission 最优解: 1(88) (这个 solution 也是 editorial 最优解):

public class Solution {  
    public int maxProfit(int[] prices) {  
        int minprice = Integer.MAX_VALUE;  
        int maxprofit = 0;  
        for (int i = 0; i < prices.length; i++) {  
            if (prices[i] < minprice)  
                minprice = prices[i];  
            else if (prices[i] - minprice > maxprofit)  
                maxprofit = prices[i] - minprice;  
        }  
        return maxprofit;  
    }  
}

这个是另外一种更容易理解的写法:

public int maxProfit(int[] prices) {  
     int min = Integer.MAX_VALUE, max = 0;  
     for (int i = 0; i < prices.length; i++) {  
         min = Math.min(min, prices[i]);  
         max = Math.max(max, prices[i] - min);  
     }  
     return max;  
 }

总体的思路还是非常类似的, 不过他把我对第二个 DP 的优化也采用到了第一个 DP 上面, 这样最后 time 被砍了一半, space 也降到了O(1); 不知道为什么我没有想到, 按说第二个 DP 我想到了为什么第一个反而没有想到?
无论如何, 在 DP 问题中节省 space 的这个通用技巧还是要会的. 这个估计经常要考到.

这个是 discussion 里面给出的一个很有意思的 followup:
The logic to solve this problem is same as "max subarray problem" using Kadane's Algorithm. Since no body has mentioned this so far, I thought it's a good thing for everybody to know.

All the straight forward solution should work, but if the interviewer twists the question slightly by giving the difference array of prices, Ex: for {1, 7, 4, 11}, if he gives {0, 6, -3, 7}, you might end up being confused.

Here, the logic is to calculate the difference (maxCur += prices[i] - prices[i-1]) of the original array, and find a contiguous subarray giving maximum profit. If the difference falls below 0, reset it to zero.

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

• maxCur = current maximum value
• maxSoFar = maximum value found so far

按照这里的代码的意思, 现在给出的 prices 里面的应该还是价格, 而不是差价.
这个人的想法还是很有意思的, 当然如果给你的真的是diff array, 你当然可以转换为 price array 然后做, 不过这个弯真正面试的时候不一定转的过来.

这个是一个改写后的版本:

public int maxProfit(int[] prices) {  
        int max = 0, min = Integer.MAX_VALUE;  
        for (int i = 0; i < prices.length; i++) {  
            if (prices[i] < min) min = prices[i];  
            else if (prices[i] > min) max = Math.max(prices[i] - min, max);  
        }  
        return max;  
}

这个其实不是 Kadane 了, 这个就是针对这个题目本身的一个代码.

Problem 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.
Difficulty:Easy
Category:Algorithms
Acceptance:40.73%
Contributor: LeetCode
Companies
amazon microsoft bloomberg uber facebook
Related Topics
array dynamic programming
Similar Questions
Maximum Subarray Best Time to Buy and Sell Stock II Best Time to Buy and Sell Stock III Best Time to Buy and Sell Stock IV Best Time to Buy and Sell Stock with Cooldown