题解 | #标记法解决子数组的最大累加和问题#

在草稿纸上可以先模拟尝试，可以观察到此问题的2个特点：
1.有效的累加和序列的首项一定为正数。
2.若在尝试序列的中途过程，出现了累加和为负的情况，则这个序列肯定不成功。

因此，可以声明布尔标记、累加和、最大值 三个变量，按如下规则进行：
1.顺次遍历数组。
2.若当前项为正，标记为true，开始累加。若标记为true，则继续往下累加。同时每次比较和更新最大值。
3.若累加和为负，则标记为false，累加和重置为0。后面的遍历中，若当前项为正，则跳回步骤2。

遍历数组完成即可得到答案。时间复杂度O(n)，空间复杂度O(1)。

java代码：

public int maxsumofSubarray (int[] arr) {
        // write code here
        int sum = 0;
        int ans = Integer.MIN_VALUE;
        boolean flag = false;
        for (int i = 0; i < arr.length; i++){
            if (flag){
                sum += arr[i];
                ans = Math.max(sum, ans);
            } else if (arr[i] > 0){
                flag = true;
                sum += arr[i];
                ans = Math.max(sum, ans);
            }
            if (sum < 0){
                sum = 0;
                flag = false;
            }
        }
        return ans;
    }