首页 > 其他 > 详细

Best Time to Buy and Sell Stock

时间:2019-04-30 22:27:02      阅读:173      评论:0      收藏:0      [点我收藏+]

149. Best Time to Buy and Sell Stock

https://www.lintcode.com/problem/best-time-to-buy-and-sell-stock/description?_from=ladder&&fromId=16

技术分享图片
public class Solution {
    /**
     * @param prices: Given an integer array
     * @return: Maximum profit
     */
    public int maxProfit(int[] prices) {
        // write your code here
        if(prices==null || prices.length==0){
            return 0;
        }
        
        int min = Integer.MAX_VALUE;
        int res = Integer.MIN_VALUE;
        for(int i=0;i<prices.length;i++){
            min = Math.min(prices[i],min);
            res = Math.max(res,prices[i]-min);
        }
        
        return res;
    }
}
View Code

 

150. Best Time to Buy and Sell Stock II

https://www.lintcode.com/problem/best-time-to-buy-and-sell-stock-ii/description?_from=ladder&&fromId=16

技术分享图片
class Solution {
    public int maxProfit(int[] prices) {
        if (prices == null || prices.length == 0) {
            return 0;
        }
        int res = 0;
        for (int i = 0; i < prices.length - 1; i++) {
            if (prices[i + 1] - prices[i] > 0) {
                res += prices[i + 1] - prices[i];
            }
        }
        return res;
    }
}
View Code

 

151. Best Time to Buy and Sell Stock III

https://www.lintcode.com/problem/best-time-to-buy-and-sell-stock-iii/description?_from=ladder&&fromId=16

技术分享图片
public class Solution {
    /**
     * @param prices: Given an integer array
     * @return: Maximum profit
     */
    public int maxProfit(int[] prices) {
        // write your code here
        if(prices==null||prices.length==0){
            return 0;
        }
        int n= prices.length;
        int[][] f = new int[n+1][5+1];
        
        f[0][0]=0;
        
        for(int i=1;i<=n;i++){
            //手中无股票
            for(int j=1;j<=5;j+=2){
                //情况1:昨日卖出
                f[i][j] = Math.max(f[i][j],f[i-1][j]);
                //情况2:昨日持有+今日卖出收益
                if(j>1 && i>1){
                    f[i][j] = Math.max(f[i][j],f[i-1][j-1]+prices[i-1]-prices[i-2]);
                }
            }
            
            //手中有股票
            for (int j = 2; j <= 2 * 2; j += 2) {
                // two option: sell or don‘t sell
                if (i > 1) {
                    //情况1:昨日持有+今日收益
                    f[i][j] = Math.max(f[i][j], f[i - 1][j] + (prices[i - 1] - prices[i - 2]));
                }
                if (j > 1) {
                    //情况2:昨日卖出
                    f[i][j] = Math.max(f[i][j], f[i - 1][j - 1]);
                }
            }
        }
        
        int res = Integer.MIN_VALUE;
        for (int j = 1; j <= 5; j += 2) {
            res = Math.max(res, f[n][j]);
        }
        
        return res;
    }
}
View Code

 

393. Best Time to Buy and Sell Stock IV

https://www.lintcode.com/problem/best-time-to-buy-and-sell-stock-iv/description?_from=ladder&&fromId=16

技术分享图片
public class Solution {
    /**
     * @param K: An integer
     * @param prices: An integer array
     * @return: Maximum profit
     */
    public int maxProfit(int K, int[] prices) {
        // write your code here
        int n = prices.length;
        if(n==0){
            return 0;
        }
        
        if(K>n/2){
            int tmp =0;
            for(int i=0;i<n-1;i++){
                tmp+=Math.max(0,prices[i+1]-prices[i]);
            }
            
            return tmp;
        }
        
        int[][]f = new int[n+1][2*K+1+1];
        
        f[0][0] = 0;
        for(int i=1;i<=n;i++){
            //不持有股票的情况
            for(int j=1;j<=2*K+1;j+=2){
                //昨日已卖出
                f[i][j] = Math.max(f[i][j],f[i-1][j]);
                if(i>=2 && j>1){  //注意要加入j>1的边界,j=1时,前一状态是不可能持有股票
                    //昨日持有,今日卖出
                    f[i][j] = Math.max(f[i][j],f[i-1][j-1]+prices[i-1]-prices[i-2]);
                }
            }
            
            //持有股票
            for(int j =2;j<=2*K;j+=2){
                //昨日已持有,需累加今日收益
                if(i>=2)
                f[i][j] = Math.max(f[i][j],f[i-1][j]+prices[i-1]-prices[i-2]);
                //昨日不持有,今日刚买入
                f[i][j] = Math.max(f[i][j],f[i-1][j-1]);
            }
        }
        
        int res = 0;
        for(int j =1;j<=2*K+1;j+=2){
            res = Math.max(res,f[n][j]);
        }
        
        return res;
    }
}
View Code

 

Best Time to Buy and Sell Stock

原文:https://www.cnblogs.com/lizzyluvcoding/p/10798136.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!