53.最大子序和

发表于 更新于 分类于 ，

题目

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

示例:

1
2
3
输入: [-2,1,-3,4,-1,2,1,-5,4],
输出: 6
解释: 连续子数组 [4,-1,2,1] 的和最大，为 6。

思路

题目要求有最大和的连续子数组,如果添加数组的下一个数导致这个和成为了负数,说明这个序列能到达的最大的长度已经结束了,因为加上下一个数只会让和变得更小,新的序列应该从下一个数开始尝试.

所以我们可以设定一个最大值,每当一个序列结束时,我们就将这个序列的和与最大值进行比较,如果序列和大于最大值,就让这个序列和成为最大值.

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public int MaxSubArray(int[] nums)
{
    if (nums.Length == 0)
    {
        return 0;
    }
    int sum = 0;
    int max = nums[0];
    for (int i = 0; i < nums.Length; i++)
    {
        sum = sum < 0 ? 0 : sum;//如果sum<0那这个sum就可以舍弃了,直接变为0;
        sum += nums[i];
        max = sum > max ? sum : max;
    }
    return max;
}