Leetcode 53. 最大子数组和

Leetcode 53. 最大子数组和

题目

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

子数组 是数组中的一个连续部分。

思路

• 设置一个result存储最大值，在设置一个count记录当前的连续子数组和
• 遍历数组，从第一个元素开始加，如果count < 0 ,说明遇到了负数，那么重新将count = 0,之后如果count > 0, 那么比较count 与 result大小，如果count > result ，更新result。

代码

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int result = INT32_MIN;// 初始化最小值
        int count = 0;// 当前最大和
        for(int i = 0; i < nums.size(); i++)
        {
            count += nums[i];

            if(count > result)
            {
                result = count;// 更新result
            }

            if(count <= 0)
            {
                count = 0;// 重新初始化
            }
        }

        return result;
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24