当前位置:新注册送38元体验金 > 新注册送38元体验金编程 > leetcode笔记(一)309. Best Time to Buy and Sell Stock w

leetcode笔记(一)309. Best Time to Buy and Sell Stock w

文章作者:新注册送38元体验金编程 上传时间:2019-08-22

leetcode笔记(一)309. Best Time to Buy and Sell Stock with Cooldown,leetcodecooldown

  • 题目描述 (原题目链接)

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

Design an algorithm to find the maximum profit. You may complete as many transactions as you like (ie, buy one and sell one share of the stock multiple times) with the following restrictions:

  • You may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again).
  • After you sell your stock, you cannot buy stock on next day. (ie, cooldown 1 day)

Example:

prices = [1, 2, 3, 0, 2]
maxProfit = 3
transactions = [buy, sell, cooldown, buy, sell]
  • 新注册送38元体验金,解题思路 (原思路链接)
这道题目自己一开始根本没有想到用动态规划,菜鸟本色。之后看了dicussion区域排名第一的答案,也是云里雾里。
还好碰到了这个解决思路。这个方案把每天分为四个状态

结合这个思路,编码实现如下:

需要额外注意的一点是第0天的初始化,(有股票,休息)= -price 因为下一天可能卖这个股票,所以计价时相当于第0天买了。

    int maxProfit(vector<int>& prices) {

        int has_sell, has_sell_before;
        int has_rest, has_rest_before;
        int no_buy, no_buy_before;
        int no_rest, no_rest_before;

        int size = prices.size();
        if(size < 2)
            return 0;
        has_sell_before = 0;
        has_rest_before = -prices[0];
        no_buy_before = -prices[0];
        no_rest_before = 0;
        for(int i = 1; i < size; i  )
        {
            has_sell = max(has_rest_before   prices[i], no_buy_before   prices[i]);
            has_rest = max(has_rest_before, no_buy_before);
            no_buy = no_rest_before - prices[i];
            no_rest = max(no_rest_before, has_sell_before);

            has_sell_before = has_sell;
            has_rest_before = has_rest;
            no_buy_before = no_buy;
            no_rest_before = no_rest;
        }

        // find the max between has_sell and no_rest
        return max(has_sell, no_rest);
    }

 

. Best Time to Buy and Sell Stock with Cooldown,leetcodecooldown 题目描述 (原题目链接) Say you have an array for which the i thelement is t...

本文由新注册送38元体验金发布于新注册送38元体验金编程,转载请注明出处:leetcode笔记(一)309. Best Time to Buy and Sell Stock w

关键词: