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}));

	}

　　输出结果为

123. Best Time to Buy and Sell Stock （三） leetcode解题笔记