Best Time to Buy and Sell Stock

121 Best Time to Buy and Sell Stock

class Solution {
    public int maxProfit(int[] prices) {
        int curMin = Integer.MAX_VALUE;
        int ans = 0;
        for(int i : prices){
            curMin = Math.min(curMin, i);
            ans = Math.max(i - curMin, ans);
        }
        return ans;
    }
}

Kadane's Algorithm-What about giving the difference?

class Solution {
    public int maxProfit(int[] prices) {
        int maxCur = 0;
        int 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;
    }
}

122.Best Time to Buy and Sell Stock II

Greedy

class Solution {
    public int maxProfit(int[] prices) {
        int ans = 0;
        for(int i = 1; i < prices.length; i++){
            if(prices[i] > prices[i - 1])
                ans += prices[i] - prices[i - 1];
        }
        return ans;
    }
}

123.Best Time to Buy and Sell Stock III

https://leetcode.com/problems/best-time-to-buy-and-sell-stock-iii/discuss/39608/A-clean-DP-solution-which-generalizes-to-k-transactions

http://bangbingsyb.blogspot.com/2014/11/leetcode-best-time-to-buy-and-sell.html

DP

How to generalizes to k transactions?

dp[k, i]The max profit up until prices[i]

do[0, i] = 0, Zero times transaction makes 0 profit

dp[k, 0] = 0

class Solution {
    public int maxProfit(int[] prices) {
        int n = prices.length; 
        int num = 2;
        if(n <= 1){
            return 0;
        }
        else{
            int[][] dp = new int[num + 1][n];
            for(int k = 1; k <= num; k++){
                // tmp current Earn so far
                // 目前的profit 
                int tmp = dp[k - 1][0] - prices[0];
                for(int i = 1; i < n; i++){
                    dp[k][i] = Math.max(dp[k][i - 1], prices[i] + tmp);
                    tmp = Math.max(tmp, dp[k - 1][i] - prices[i]);
                }
            }
            return dp[num][n - 1];
        }
    }
}

if num = 1;
dp[0][] = 0;
dp[1][]

188.Best Time to Buy and Sell Stock IV

class Solution {
    public int maxProfit(int k, int[] prices) {
        int n = prices.length;
        if(n <= 1)
            return 0;
        if(2 * k >= n ){
            //We can do as many trasactions as we can;
            //Reduced the question to Question II;
            //if k >= n/2, then you can make maximum number of transactions.

            int ans = 0;
            for(int i = 1; i < n; i++){
                int diff = prices[i] - prices[i - 1];
                ans += diff > 0 ? diff : 0;
            }
            return ans;
        }
        else{
            int[][] dp = new int[k + 1][n];
            for(int i = 1; i <= k; i++){
                int tmp = dp[i - 1][0] - prices[0];
                for(int j = 1; j < n ; j++){
                    dp[i][j] = Math.max(dp[i][j - 1], tmp + prices[j]);
                    tmp = Math.max(tmp, dp[i - 1][j] - prices[j]);
                }
            }
            return dp[k][n - 1];
        }
    }
}