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

方法：动态规划

public class Solution {

    public int maxsumofSubarray(int[] arr) {
        int len = arr.length;
        // dp[i] 表示：以 nums[i] 结尾的数组的长度
        int[] dp = new int[len];
        dp[0] = arr[0];
        int res = arr[0];
        for (int i = 1; i < len; i++) {
            dp[i] = Math.max(dp[i - 1] + arr[i], arr[i]);
            res = Math.max(res, dp[i]);
        }
        return res;
    }
}

复杂度分析：

• 时间复杂度：，这里 是数组的长度；
• 空间复杂度：。

时间复杂度做到最优就可以了。空间复杂度还可以使用「滚动变量」进行优化。