ChunNote
0%

leetCode-53:Maximum Subarray

发表于 分类于

问题描述

给定一个整数数组，要求找出其连续子数组的最大和。题目链接：**点我**

样例输入输出

输入：[-2,1,-3,4,-1,2,1,-5,4]

输出：6

解释：对应子数组为：[4,-1,2,1]

输入：[1]

输出：1

问题解法

遍历数组，取累计数和与当前结果值的最大值作为本轮更新后的结果值。同时判断当前累计数的和，如果是正数，则将当前数放入累计和里，如果是负数，说明当前数是一个比较大的负数，则将当前累计和清零，方便下一轮比较。代码如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution
{
    public int maxSubArray(int[] nums)
    {
        int sum = 0;
        int result = nums[0];
        for (int i = 0; i < nums.length; i++)
        {
            result = Math.max(sum + nums[i], result);
            if (sum + nums[i] > 0)
            {
                sum = sum + nums[i];
            }
            else
            {
                sum = 0;
            }
        }
        
        return result;
    }
}