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

/** * RECOMMENDED CONFIGURATION VARIABLES: EDIT AND UNCOMMENT THE SECTION BELOW TO INSERT DYNAMIC VALUES FROM YOUR PLATFORM OR CMS. * LEARN WHY DEFINING THESE VARIABLES IS IMPORTANT: https://disqus.com/admin/universalcode/#configuration-variables*/ /* var disqus_config = function () { this.page.url = PAGE_URL; // Replace PAGE_URL with your page's canonical URL variable this.page.identifier = PAGE_IDENTIFIER; // Replace PAGE_IDENTIFIER with your page's unique identifier variable }; */ (function() { // DON'T EDIT BELOW THIS LINE var d = document, s = d.createElement('script'); s.src = 'https://chenzz.disqus.com/embed.js'; s.setAttribute('data-timestamp', +new Date()); (d.head || d.body).appendChild(s); })();