题解 | #买卖股票的最好时机(二)#

买卖股票的最好时机(二)

http://www.nowcoder.com/practice/9e5e3c2603064829b0a0bbfca10594e9

本题首先要清楚两点:

只有一只股票

当前只有买股票或者买股票的操作

想获得利润至少要两天为一个交易单元

这道题目可能我们只会想,选一个低的买入,在选个高的卖,在选一个低的买入.....循环反复。

如果想到其实最终利润是可以分解的,那么本题就很容易了!

如何分解呢?

假如第0天买入,第3天卖出,那么利润为:prices[3] - prices[0]。

相当于(prices[3] - prices[2]) + (prices[2] - prices[1]) + (prices[1] - prices[0])。

此时就是把利润分解为每天为单位的维度,而不是从0天到第3天整体去考虑!

那么根据prices可以得到每天的利润序列:(prices[i] - prices[i - 1]).....(prices[1] - prices[0])。

alt

一些同学陷入:第一天怎么就没有利润呢,第一天到底算不算的困惑中。

第一天当然没有利润,至少要第二天才会有利润,所以利润的序列比股票序列少一天!

从图中可以发现,其实我们需要收集每天的正利润就可以,收集正利润的区间,就是股票买卖的区间,而我们只需要关注最终利润,不需要记录区间。

那么只收集正利润就是贪心所贪的地方!

局部最优:收集每天的正利润,全局最优:求得最大利润。

局部最优可以推出全局最优,找不出反例,试一试贪心!

对应的C++代码块

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int result = 0;
        for (int i = 1; i < prices.size(); i++) {
            result += max(prices[i] - prices[i - 1], 0);
        }
        return result;
    }
};

对应的JAVA代码

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
     * 计算最大收益
     * @param prices int整型一维数组 股票每一天的价格
     * @return int整型
     */
    public int maxProfit (int[] prices) {
        // write code here
        int result=0;
        for(int i=1;i<prices.length;i++){
            result+=Math.max(prices[i]-prices[i-1],0);
        }
        return result;
    }
}
全部评论

相关推荐

双非鼠鼠会梦到大厂offer:太难了,感同身受
投递美团等公司10个岗位
点赞 评论 收藏
分享
1 收藏 评论
分享
牛客网
牛客企业服务