题目描述

给定一个数组arr，返回子数组的最大累加和
例如，arr = [1, -2, 3, 5, -2, 6, -1]，所有子数组中，[3, 5, -2, 6]可以累加出最大的和12，所以返回12.
题目保证没有全为负数的数据
[要求]
时间复杂度为O(n)，空间复杂度为O(1)

示例

输入

[1, -2, 3, 5, -2, 6, -1]

输出

12

解题思路

  1. 将问题拆解为最小问题，拿最上面的示例举例，假若数组只有 [1, -2]，当遍历到 -2 时，子数组和为 -1 ，最大和可以一眼看出是 1。假若数组增加一个元素 3，即 [1, -2, 3]，根据上面已得出的 [1, -2] 子数组和为 -1 的结论，可得当前子数组和为 3 - 1 = 2，尽管 2 比上一次的最大和 1 还要大，但结果却比新加进来的 3 本身还要小，这并不是我们想要的，于是我们直接取 3 为最大子数组和。
  2. 根据上面的现象，我们可以推出，遍历数组 arr，如果 arr[i] 与前面的子数组之和相加，结果比 arr[i] 要大，那么 arr[i] 前面的子数组与 arr[i] 结合，成为一个新的子数组，否则 arr[i] 独自成为一个子数组。
  3. 因为题目要求了时间复杂度和空间复杂度，所以我们要合理重复利用系统提供的数组。

Java代码实现

public class Solution {
    public int maxsumofSubarray (int[] arr) {
        // 若数组为空，返回0；若数组只有1个元素，返回那个元素
        if (arr == null || arr.length == 0) return 0;
        else if (arr.length == 1) return arr[0];
        // max记录最大子数组和
        int max = 0;
        // 记录每个位置与之前子集的加和
        for (int i = 1; i < arr.length; ++i) {
            arr[i] = arr[i] > arr[i] + arr[i-1] ? arr[i] : arr[i] + arr[i-1];
            max = arr[i] > max ? arr[i] : max;
        }
        return max;
    }
}