#121 买卖股票的最佳时机(动态规划|分治)

121. 买卖股票的最佳时机 - 力扣（LeetCode）

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        vector<vector<int>> dp(prices.size(), vector<int>(prices.size(), 0));
        int max = 0;
        for (int i = 0; i < prices.size(); i++)
            for (int step = 1; i + step < prices.size(); step++) {
                dp[i][i + step] = dp[i][i + step - 1] +prices[i + step]-prices[i + step-1];
                if (dp[i][i + step] > max) max = dp[i][i + step];
            }
        return max>0?max:0;
    }
};

dp[i][j]用于描述i买j卖得到的收益，超出内存限制。

股票时机是算法导论中分治问题的一个案例，将价格转化为利润，然后计算最大连续子数组。

class Solution {
public:
    int getMidMaxSubArr(vector<int>& arr, int low, int high, int mid) {
        if (low > high) return 0;
        int sum = arr[mid];
        int maxsum = sum;
        for (int i = mid - 1; i >= low; i--) {
            sum += arr[i];
            if (sum > maxsum) maxsum = sum;
        }
        sum = maxsum;
        for (int i = mid + 1; i <= high; i++) {
            sum += arr[i];
            if (sum > maxsum) maxsum = sum;
        }
        return maxsum;
    }

    int getMaxSubArr(vector<int>& arr, int low, int high) {
        if (low > high) return 0;
        int mid = (low + high) / 2;
        int leftsum = getMaxSubArr(arr, low, mid - 1);
        int rightsum = getMaxSubArr(arr, mid + 1, high);
        int midsum = getMidMaxSubArr(arr, low, high, mid);
        if (leftsum > midsum && leftsum > rightsum) return leftsum;
        else if (midsum > rightsum) return midsum;
        else return rightsum;
    }

    int maxProfit(vector<int>& prices) {
        vector<int> df(prices.size(),0);
        //df[0] should be zero
        for(int i=1;i<df.size();i++)
            df[i]=prices[i]-prices[i-1];
        return getMaxSubArr(df,0,df.size()-1);
    }
};

最大连续子数组的和不一定是正数，最后返回时应当判断，但是判题输入似乎没有出现该情况。