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

import java.util.*;


public class Solution {
    /**
     * max sum of the subarray
     * @param arr int整型一维数组 the array
     * @return int整型
     */
    public int maxsumofSubarray (int[] arr) {
        // write code here
        int m = arr.length;
        int[] dp = new int[m];
        Arrays.fill(dp, Integer.MIN_VALUE);
        int maxSum = Integer.MIN_VALUE;
        for(int i=0;i<m;i++){
            dp[i] = getDp(arr, i, dp);
            maxSum = Math.max(maxSum, dp[i]);
        }
        return maxSum;

    }

    public int getDp(int[] arr, int n, int[] dp){
        if(n == 0) return arr[0];
        if(dp[n]!=Integer.MIN_VALUE) return dp[n];
        return Math.max(arr[n], dp[n-1]+arr[n]);
    }
}