LeetCode: Maximum Subarray

题目

https://oj.leetcode.com/problems/maximum-subarray/

分析

  1. 一开始想用穷举法找出所有的子序列, 并求出最大的和,然后结果是超时了。

  2. 后来发现这道题是一道很巧妙的DP题,

首先我们先来求另一个问题, “数组A[]中包含最后一个元素的最大连续子序列的和为多少?”

包含最后一个元素的最大连续子序列的和有两种情况: 

最后一个元素和前面的元素构成一个子序列

或者最后一个元素自成一个子序列。

递归的求包含最后一个元素的最大连续子序列就是  f(n) = max(f(n-1), A[n]);

以此类推, 每个元素为结尾的最大连续子序列的和就求出来了,

  1. 在2中, 其中的最大值便是整个数列的最大连续子序列的和。

把上面递归用改写为递归的形式, 就是最终结果了。

代码

class Solution
{
public:
    int maxSubArray(int A[], int n)
    {
        int sum[n], res;

        sum[0] = A[0];
        res = sum[0];
        for (int i = 1; i < n; i++)
        {
            sum[i] = max(A[i], sum[i-1] + A[i]);
            res = max(res, sum[i]);
        }

        return res;
    }
};

参考

http://blog.csdn.net/v_july_v/article/details/6444021

本文章迁移自http://blog.csdn.net/timberwolf_2012/article/details/39271637