Leetcode_123_Best Time to Buy and Sell Stock III

时间:2021-07-01 07:21:09

本文是在学习中的总结,欢迎转载但请注明出处:http://blog.csdn.net/pistolove/article/details/43740415


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).

思路:

(1)题意为给定一个数组,数组中第i个元素的值对应着第i天的股票,最多只能进行两次交易,每次交易只能买入一次并卖出,求能得到的最大利润。该题为Best Time to Buy and Sell StockBest Time to Buy and SellStockⅡ的加强版。

(2)该题同样考查的是最大差值,但是与前面类似的两题有较大的区别。由于最多只能进行两次交易,假设在数组中存在4个点(其中数组长度大于等于4)a,b,c,d四个点使得到最值,其中a<b<=c<d,f(max)=(d-c) + (b-a),这样可以从任意位置x将数组分为两个区间,分别为0~x和x~len-1。考虑将两个区间的值保存在两个不同的数组中,通过遍历整个数组,就得到了任意点经过两次交易的分布在两个数组中的利润值,然后遍历这两个数组,同一位置上相加得到的最大值即为所得结果。详情见下方代码。

(3)希望本文对你有所帮助。

算法代码实现:

/**
 * @author liqq
 */
public class Solution {
	public int maxProfit(int[] x) {
		if (x == null || x.length <= 1)
			return 0;

		int[] right = new int[x.length];
		int[] left = new int[x.length];

		int rmin = x[0];

		for (int i = 1; i < x.length; i++) {
			rmin = Math.min(rmin, x[i]);
			right[i] = Math.max(right[i - 1], x[i] - rmin);
		}

		int lmax = x[x.length - 1];
		left[x.length - 1] = 0;
		for (int i = x.length - 2; i >= 0; i--) {
			lmax = Math.max(lmax, x[i]);
			left[i] = Math.max(left[i + 1], lmax - x[i]);
		}

		int sum = 0;
		for (int i = 0; i < x.length; i++) {
			sum = Math.max(sum, right[i] + left[i]);
		}
		return sum;
	}
}