lc 买卖股票的最佳时机

链接：https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock/

代码：

#include<iostream>
#include<algorithm>
class Solution {
public:
    int maxProfit(vector<int>& prices) {
        vector<int> a = prices;
        int length = prices.size();
        if(length == 0) return 0;
        a[0] = 0;
        int ans = 0;
        for(int i = 1; i < prices.size(); i++) {
            a[i] = prices[i] - prices[i-1];
        }
        // for(int i = 0; i < prices.size(); i++) {
        //     cout << a[i] << " ";
        // }
        // cout << endl;
        ans = solve(a, 0, length-1);
        return ans;
    }
    int solve(vector<int>& prices, int low, int high) {
        // for(int i = 0; i < prices.size(); i++) {
        //     cout << prices[i] << " ";
        // }
        // cout << endl;
        if(low == high) return prices[low];
        int mid = (low + high) / 2;
        int s1 = solve(prices, low, mid);
        // cout << "=====" << endl;
        int s2 = solve(prices, mid+1, high);
        int s3 = through_mid(prices, mid);
        return max(max(s1, s2), s3);
    }
    int through_mid(vector<int>& prices, int mid) {
        // for(int i = 0; i < prices.size(); i++) {
        //     cout << prices[i] << " ";
        // }
        // cout << endl;
        // cout << mid << endl;
        int forward = 0;
        int backward = 0;
        int formax = -1;
        int backmax = -1;
        for(int i = mid; i >= 0; i--) {
            forward += prices[i];
            if(formax < forward) formax = forward;
        }
        if(formax < 0) formax = 0;
        for(int i = mid; i < prices.size(); i++) {
            backward += prices[i];
            if(backmax < backward) backmax = backward;
        }
        if(backmax < 0) backmax = 0;
        // cout << formax << " " << backmax << endl;
        if(prices[mid] > 0) return formax + backmax - prices[mid];
        else return formax + backmax;
    }
};

思路：可归并，可dp。

先说归并，先预处理增量数组，划分子问题然后看从下到上如何合并。将一线段一分为二，要不出现“买卖”1.出现在前半段，要不 2.出现在后半段，要么3.“买”在前半段，“卖”在后半段。前两种情况只不过是规模小一点但性质完全相同的子问题，若想合并，还需要处理第三种情况。从分点开始向前找一个最小，向后找一个最大，合起来第三种情况解决。取三种情况中的最小值问题得以解决。

dp，先预处理增量数组，若dp[i] < 0, dp[i] = 0 相当于前面的取点作废，重新开始；dp[i] = dp[i-1] + increase[i]。相当于状态转移方程是 dp[i] = max(0,dp[i-1]+increase[i])。