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

此文仅用于本人记录

我一看是动态规划就列dp了，结果啊没想到是搞复杂了，直接在原数组基础上搞状态数组和状态转移方程就行了：

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 result = arr[0];
        for(int i = 1;i < arr.length;i++){
            arr[i] = Math.max(arr[i],arr[i-1]+arr[i]);
            result = Math.max(arr[i],result);
        }
        return result;
    }
}

这行代码是关键：

arr[i] = Math.max(arr[i],arr[i-1]+arr[i]);

他表示当前数组被改造成了每个元素要么是本身，要么是前面n位所能得到的连续最大和加上本身（为什么是连续最大和而不是最大和呢？因为可能存在一个超级大的负数将前面的和全部抵消）。
接下来只需要求出每位元素能达到的最大值就行啦。