子数组的最大累加和问题

描述

给定一个数组arr，返回子数组的最大累加和
例如，arr = [1, -2, 3, 5, -2, 6, -1]，所有子数组中，[3, 5, -2, 6]可以累加出最大的和12，所以返回12.
题目保证没有全为负数的数据

要求

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

思路

只要数组前面累加的总和sum大于0，就值得继续往下累加，记录累加的总和sum。否则就放弃前面累加的数，重新进行累加。每一次累加完都记录最大值max，最后进行输出，得到的即为所求。

    public int maxsumofSubarray (int[] arr) {
        //记录当前总和
        int sum = 0;
        //记录最大总和
        int max = 0;
        //遍历数组
        for (int i = 0; i < arr.length; i++) {
            //如果当前的总和大于等于0，就继续累加，否则就重新开始累加
                sum = sum>=0? sum + arr[i]:arr[i];
            //记录最大值
                max = sum>max? sum:max;
        }    
        return max;
    }