123. Best Time to Buy and Sell Stock (三) leetcode解题笔记

123. Best Time to Buy and Sell Stock III

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 at most two transactions.

Note:
You may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again).

让我们看看它又耍了什么新花样 还是找最大利润  但是只允许你交易两次 还是在买之前必须把之前买的卖出去

没思路。。  有点棘手。。

能在遍历一遍的情况下得到解吗  感觉可以。。想一会先

怎么感觉这种题好适合股票啊 。。完全没思路

还是维护一个最小值 和 利润值  交易过后重置最小值  同时维护最大的两个利润值?

没思路 去discuss区看看大神怎么解的- -

public class Solution {
    public int maxProfit(int[] prices) {
        int hold1 = Integer.MIN_VALUE, hold2 = Integer.MIN_VALUE;
        int release1 = 0, release2 = 0;
        for(int i:prices){                              // Assume we only have 0 money at first
            release2 = Math.max(release2, hold2+i);     // The maximum if we‘ve just sold 2nd stock so far.
            hold2    = Math.max(hold2,    release1-i);  // The maximum if we‘ve just buy  2nd stock so far.
            release1 = Math.max(release1, hold1+i);     // The maximum if we‘ve just sold 1nd stock so far.
            hold1    = Math.max(hold1,    -i);          // The maximum if we‘ve just buy  1st stock so far.
        }
        return release2; ///Since release1 is initiated as 0, so release2 will always higher than release1.
    }
}

  空间复杂度o(1) 时间复杂度o(n)

理解一下各个字段 hold1 买入第一个商品的当前最大值 hold2买入第二个商品的当前最大值  release1卖出第一个商品的当前最大值  release2卖出第二个商品的当前最大值

不是很理解  决定在eclipse设置一个案例试试。

给定的数组为2,5,8,3,18,12,6,53,59,11

public static void main(String[] args){
		test test =new test();
		test.Solution solution=test.new Solution();
		System.out.print(solution.maxProfit(new int[]{2,5,8,3,18,12,6,53,59,11}));
	}

  输出结果为

看看调试中这四个变量的变化 在Hold1前设置断点

读入第一个数2 没什么大变化

读入第二个数5 release1和release2变成3

省略一些  读到18时看看各个值

release2就是目前阶段的解。。。   看不懂 先这样吧 - -

时间: 10-26

123. Best Time to Buy and Sell Stock (三) leetcode解题笔记的相关文章

188. Best Time to Buy and Sell Stock IV leetcode解题笔记

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 at most k transactions. Note:You may not engage in multiple transactions at the same time (ie, yo

123. Best Time to Buy and Sell Stock III

/* * 123. Best Time to Buy and Sell Stock III * 2016-5-21 by Mingyang * 根据题目要求,最多进行两次买卖股票,而且手中不能有2只股票,就是不能连续两次买入操作. * 所以,两次交易必须是分布在2各区间内,也就是动作为:买入卖出,买入卖出. * 进而,我们可以划分为2个区间[0,i]和[i,len-1],i可以取0~len-1. * 那么两次买卖的最大利润为:在两个区间的最大利益和的最大利润. * 一次划分的最大利益为:Prof

LeetCode121/122/123 Best Time to Buy and Sell Stock<股票> I/II/III----DP+Greedy**

一:LeetCode 121 Best Time to Buy and Sell Stock 题目: 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), d

Best Time to Buy and Sell Stock III leetcode java

题目: 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 at most two transactions. Note: You may not engage in multiple transactions at the same time

Best Time to Buy and Sell Stock II leetcode java

题目: 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)

LeerCode 123 Best Time to Buy and Sell Stock III之O(n)解法

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 at most two transactions. Note: You may not engage in multiple transactions at the same time (ie,

[LeetCode] 123. Best Time to Buy and Sell Stock III 买卖股票的最佳时间 III

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 at most two transactions. Note:You may not engage in multiple transactions at the same time (ie,

123. Best Time to Buy and Sell Stock III ~~

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 at most two transactions. Note:You may not engage in multiple transactions at the same time (ie,

Leetcode 123. Best Time to Buy and Sell Stock III JAVA语言

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 at most two transactions. Note: You may not engage in multiple transactions at the same time (ie,