LeetCode053（最大子序和）

发表于 | 分类于 ，

题目：

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

思路：

　　此题没有明显的递推式，但总体问题的最优解依赖于子问题的最优解。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
// DP
   public int maxSubArray(int[] nums) {
	int ans = nums[0];
	int sum = 0;
	for(int num:nums) {
		if (sum > 0) {
			sum += num;
		}else {
			sum = num;
		}
		ans = Math.max(ans, sum);
	}
	return ans;
   }

复杂度分析：

动态规划：

　　时间复杂度：
　　　　O(n)。
　　空间复杂度：
　　　　O(1)。