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).
题目解析:
方案一:
题目要求最多两次,要么一次要么两次。怎么去求呢?既然不一定非要两次,我们可以从i位置分开[0...i] [i...n],左边求一次,右边求一次,两次求和,当i=0或i=n的时候,求解一次。这样就满足了题意。也正是因为两次是不能重叠的,所有可以分开。而每一次求的时候,利用Best
Time to Buy and Sell Stock的线性方案。要循环n次,所以时间复杂度为O(n^2)。会超时。
class Solution { public: int maxProfit(vector<int> &prices) { int len = prices.size(); if(len <= 1) return 0; int max = 0; for(int i = 0;i < len;i++){ int sum = OneProfit(prices,0,i) + OneProfit(prices,i,len-1); max = max > sum ? max : sum; } } int OneProfit(vector<int> &prices,int begin,int end) { if(begin >= end) return 0; int res = 0; int min = prices[begin]; for(int i = begin;i <= end;i++){ if(prices[i] < min) min = prices[i]; else{ if(prices[i]-min > res) res = prices[i]-min; } } return res; } };
方案二:
我们从[0...i]求出最大值后,如果快速推出[0...i+1]呢?可以让函数返回一个最小值,求a[i+1]-min,再判断是否更新收益。但如何求解[i...n]推出[i+1...n]呢?这样看似不可能的,但我们反过来求,让r[i]表示r[i...n]的最大收益,而不是r[0...i]的最大收益。
将正向数组和反向数组都求出后,直接l[i]+r[i]就是我们要求的在第i个位置分割的最大收益。
这个思想很好,没有逆向思维是不容易想出来的。要加强这方面的考虑。
class Solution { public: int maxProfit(vector<int> &prices) { // Start typing your C/C++ solution below // DO NOT write int main() function int profit = 0, n = prices.size(); if (n == 0) { return 0; } int l[n], r[n]; memset(l, 0, sizeof(int) * n); memset(r, 0, sizeof(int) * n); int min = prices[0]; for (int i = 1; i < n; i++) { l[i] = prices[i] - min > l[i - 1] ? prices[i] - min : l[i - 1]; min = prices[i] < min ? prices[i] : min; } int max = prices[n - 1]; for (int i = n - 2; i >= 0; i--) { r[i] = max - prices[i] > r[i + 1] ? max - prices[i] : r[i + 1]; max = prices[i] > max ? prices[i] : max; } for (int i = 0; i < n; i++) { profit = l[i] + r[i] > profit ? l[i] + r[i] : profit; } return profit; } };