leetcode笔记:Maximum Subarray(最大子串和问题)

来源:转载

一. 题目描述

Find the contiguous subarray within an array (containing at least one number) which has the largest sum.

For example, given the array

[−2,1,−3,4,−1,2,1,−5,4]
, the contiguous subarray
[4,−1,2,1]
has the largest
sum = 6
.

二. 题目分析

可使用动态规划来解决。时间复杂度为O(n)。假设已知
0, .., k
的最大和
sum[k]
以后,则
0, ..., k+1
的最大和sum[k+1]分为以下两种情况:

1)若
sum[k]>=0
,则
sum[k+1]=sum[k]+A[k+1]


2)若
sum[k]<0
,另起一个SubArray,令
sum[k+1]=A[k+1]


在计算过程中,使用一个变量
maxsum
用于存储
sum
的最大值,一旦出现更大的
sum
值则更新之,最后返回该变量即可。

三. 示例代码

[code]int maxSubArray(int A[], int n) { if (n <= 0) return 0; int sum = 0; int maxsum = INT_MIN; for (int i = 0; i < n; i++) {sum += A[i];if (sum > maxsum) maxsum = sum;if (sum < 0) sum = 0; } return maxsum; }


四. 小结

该题是一道基础的动态规划题,尽管有多种其他方法可以实现。

参考:leetcode笔记:Maximum Subarray(最大子串和问题)
http://www.lai18.com/content/1364383.html



分享给朋友:
您可能感兴趣的文章:
随机阅读: