题解 | #子数组的最大累加和问题#

import java.util.*;


public class Solution {
    /**
     * max sum of the subarray
     * @param arr int整型一维数组 the array
     * @return int整型
     */
    public int maxsumofSubarray (int[] arr) {

        if (arr.length == 0) {
            return arr[0];
        }

        int max = arr[0];
        int sum = arr[0];

        /***
         * 该题的本质是一个个往后累加，若过程中累加和小于0，那么就需要将前面的数都舍掉，继续重新从下一个数累加，
         * 过程中需要保存累加的最大值，若加上后一个数大于前面的值，则对最大值重新赋值，反之则不变。
         */
        for (int i = 1; i < arr.length; i++) {

            if (sum < 0) {
                sum = arr[i];
            } else {
                sum = sum + arr[i];
            }

            max = Math.max(max, sum);
        }

        return max;
    }
}