原题

LintCode 41. Maximum Subarray

Description

Given an array of integers, find a contiguous subarray which has the largest sum.

Notice

The subarray should contain at least one number.

Example

Given the array [−2,2,−3,4,−1,2,1,−5,3], the contiguous subarray [4,−1,2,1] has the largest sum = 6.

解题

动态规划问题，很容易可以得到状态转移方程：
dp[i] = MAX( dp[i - 1], dp[i - 1] + A[i] )
因为实际上只会用到上一次的状态，所以只需要一个变量（而不是数组）即可存储。

class Solution {
public:
    /**
    * @param nums: A list of integers
    * @return: A integer indicate the sum of max subarray
    */
    int maxSubArray(vector<int> nums) {
        // write your code here
        if (nums.size() <= 0) return 0;
        int ans = INT_MIN, sum = 0;
        for (int i = 0; i < nums.size(); i++) {
            sum += nums[i];
            ans = max(ans, sum);
            // 当sum<0时 要置位0 意味着抛弃前i个数 从i+1开始计算
            sum = max(0, sum);
        }
        return ans;
    }
};

拓展

采用分治法解决。
假如我们将数组二分，那么最优解有三种情况

• 最优解在左子数组
• 最优解在右子数组
• 最优解跨越了左右子数组

前两种情况比较容易解决，第三种情况的做法就是从分割点开始向两边扫描，得出该种情况的最优解。
最后将三种情况的解比较得出最优解。

class Solution {
public:
    /**
    * @param nums: A list of integers
    * @return: A integer indicate the sum of max subarray
    */
    int maxSubArray(vector<int> nums) {
        // write your code here
        if (nums.size() <= 0) return 0;
        int ans = INT_MIN, sum = 0;
        for (int i = 0; i < nums.size(); i++) {
            sum += nums[i];
            ans = max(ans, sum);
            sum = max(0, sum);
        }
        return ans;
    }
    int helper(vector<int>& nums, int left, int right) {
        if (left >= right) return nums[left];
        int mid = left + (right - left) / 2;
        // 获得情况一的最优解
        int leftMax = helper(nums, left, mid - 1);
        // 获得情况二的最优解
        int rightMax = helper(nums, mid + 1, right);
        // 从分割点向两边扫描，获得情况三的最优解
        int midMax = nums[mid], sum = midMax;
        for (int i = mid - 1; i >= left; i--) {
            sum += nums[i];
            midMax = max(midMax, sum);
        }
        sum = midMax;
        for (int i = mid + 1; i <= right; i++) {
            sum += nums[i];
            midMax = max(midMax, sum);
        }
        // 比较三种情况 获得最优解
        return max(leftMax, max(midMax, rightMax));
    }
};