算法刷题目数组和矩阵
Source
Edit
History

子数组的最大累加和

子数组的最大累加和

一、题目

给定一个数组，返回数组的最大累加和

1
2
arr = {1, -2, 3, 5, -2, 6, -1}
子数组 {3, 5, -2, 6} 可以累加出最大的和为 12

二、思路

这个数组中有正数、负数。既然只是要求最大累加和。那么我们使用 cur 记录当前子数组的累加和，用 max 来记录子数组的最大累加和。

遍历这个数组，每次给 cur 加上当前这个数。如果 cur 大于 0，我们更新一下 max 的值；如果 cur 小于 0，我们给 cur 赋 0。为什么这么做呢？因为 cur 大于 0，为正数，那么肯定可以作为子数组的一部分。如果 cur 为负数了，那么它就不能作为子数组的一部分。牢记子数组是连续的，而且我们也已经用 max 再每次遍历中记录了子数组的累加和。

三、代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
#include <vector>
#include <iostream>

class Solution {
public:
    int get_max_sum(const std::vector<int>& arr) {
        int max = 0;
        int cur = 0;
        for (size_t i = 0; i < arr.size(); ++i) {
            cur += arr[i];
            if (cur > 0) {
                max = std::max(max, cur);
            } else if (cur < 0) {
                cur = 0;
            }
        }
        return max;
    }
};

int main() {
    Solution s;
    std::vector<int> arr{1, -2, 3, 5, -2, 6, -1};
    int res = s.get_max_sum(arr);
    std::cout << res << std::endl;
    return 0;
}

时间复杂度为 O(n)，空间复杂度 O(1)