LeetCode - 123. Best Time to Buy and Sell Stock III - 思路详解

LeetCode - 123. Best Time to Buy and Sell Stock III - 思路详解 - C++

本文主要是介绍LeetCode - 123. Best Time to Buy and Sell Stock III - 思路详解 - C++，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目

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.

翻译

假设一个数组，表示第i天的股票价格。设计算法，求出最大收益，最多可以进行两次交易

思路

代码

class Solution {
public:int maxProfit(vector<int>& prices) {int res = 0;int len = prices.size();if(len <= 0){return 0;}vector<int> left(len,0);vector<int> right(len,0);maxProfitLeft(prices,left);maxProfitRight(prices,right);for(int i = 0; i < len; i++){int l = left[i];int r = i+1 < len ? right[i+1]:0; int t = l+r;if(t > res){res = t;}}return res;}//采用 Best Time to Buy and Sell Stock Ivoid maxProfitLeft(vector<int> &prices,vector<int> &left){int buyPrice = prices[0];int max = 0;for(int i = 0; i < prices.size(); i ++ ){if(prices[i] < buyPrice){buyPrice = prices[i];}else{int p = prices[i] - buyPrice;if(p > max){max = p;}}left[i] = max;}}//采用 Best Time to Buy and Sell Stock Ivoid maxProfitRight(vector<int> &prices,vector<int> &right){int sellPrice = prices[prices.size()-1];int max = 0;for(int i = prices.size()-1; i >= 0; i -- ){if(prices[i] > sellPrice){sellPrice = prices[i];}else{int p = sellPrice - prices[i];if(p > max){max = p;}}right[i] = max;}}
};