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;
    }
}