leetcode_maximum_subarray

发表于

难度：Medium

分治法：找到数组的中心点mid，则最大连续元素和可能产生在：左侧子数组、右侧子数组、跨过中心点的数组。

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        return find_recursive(nums,0,nums.size()-1);
    }
    int find_recursive(vector<int>& nums, int left,  int right)
    {
        if(left == right)
            return nums[left];
        else if(left > right)
            return 0;
        int mid = left + (right-left)/2;
        int max_left = find_recursive(nums, left, mid);
        int max_right = find_recursive(nums, mid+1, right);
        int max_mid = find_sub_array_with_middle(nums,left,mid,right);
        int ret = max(max_left, max_right);
        ret = max(ret,max_mid);
        return ret;
    }
    int find_sub_array_with_middle(vector<int>& nums, int left, int mid, int right)
    {
        int sum_left = INT_MIN;
        int sum = 0;
        for(int i = mid; i >= left; i--)
        {
            sum += nums[i];
            if(sum > sum_left)
                sum_left = sum;
        }
        sum = 0;
        int sum_right = INT_MIN;
        for(int i = mid+1 ; i <= right; i++)
        {
            sum += nums[i];
            if(sum > sum_right)
                sum_right = sum;
        }
        return sum_left+sum_right;
    }
};

运行时间：22ms，超过2.14%

动态规划：遍历数组，假设以i-1结尾的最长连续元素之和为local，则以i结尾的最长连续元素之和为max(nums[i],local+nums[i])。维护一个全局最大global，每一步进行更新。
代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int local = nums[0];
        int global = nums[0];
        for(int i = 1; i < nums.size(); i++)
        {
            local = max(nums[i], local+nums[i]);
            global = max(local,global);
        }
        return global;
    }
};

运行时间：9ms，超过31.16%

ref：http://blog.csdn.net/linhuanmars/article/details/21314059