qiaoxu123
11/7/2018 - 12:15 AM

53. Maximum Subarray

给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

示例:

输入: [-2,1,-3,4,-1,2,1,-5,4], 输出: 6 解释: 连续子数组 [4,-1,2,1] 的和最大，为 6。

参考链接：https://blog.csdn.net/DERRANTCM/article/details/46736967 剑指offer面试题42

test1.cpp
content_copyfile_download
//思路：累积和（prefix_sum）
//时间：8 ms
class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        if (nums.size() < 0) return 0;
        int prefix_sum = 0;
        int min_sum = 0;
        int result = INT_MIN;
        for (auto n : nums) {
            prefix_sum += n;
            result = max(result, prefix_sum - min_sum);
            min_sum = min(prefix_sum, min_sum);
        }
        return result;
    }
};
test2.cpp
content_copyfile_download
//思路：动态规划（dynamic programming）
//时间：8 ms
class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        if (nums.size() < 0) return 0;
        int n = nums.size();
        vector<int> dp(n, 0);
        dp[0] = nums[0];
        for (int i = 1; i != n; ++i) {
            dp[i] = max(0, dp[i-1]) + nums[i]; 
        }
        int max_value = INT_MIN;
        for (auto v : dp) {
            max_value = max(v, max_value);
        }
        return max_value;
    }
};
test3.cpp
content_copyfile_download
//思路：贪心算法（greedy solution）
//时间：8 ms
class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        if (nums.size() == 0) return 0;
        int n = nums.size();
        int sum = 0;
        int slice = INT_MIN;
        for (auto n : nums) {
            sum += n;
            slice = max(sum, slice);
            sum = max(0, sum);
        }
        return slice;
    }
};
test4.cpp
content_copyfile_download
//思路：剑指offer
//时间：12 ms
class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int maxSum = INT_MIN;
        int sum = 0;
        for(int i = 0;i < nums.size();++i){
            if(sum <= 0)
                sum = nums[i];
            else
                sum += nums[i];
            if(sum > maxSum)
                maxSum = sum;
        }
        return maxSum;
    }
};