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

初始思路：
子数组的起点从0-len，循环len次，
在每次循环中，子数组终点从起点移动到arr[len]，计算子数组的和，使用max暂存最大值；
但是这样时间O（n^2）。
考虑对计算过程化简：
列出初始暴力思路的计算过程，可以发现，在终点坐标为K位置的子数组的最大值，取决于终点位置为k-1位置的子数组的最大值连接arr[k]和arr[k]的比较；
即 dp[k] = max{ dp[k-1]+arr[k] , arr[k]}
因此 dp[0]=arr[0]
dp[1]=max{ dp[0]+arr[1],arr[1]}
......
以此类推，可以得出如下代码：
注意：dp[k]的定义为终点为k的子数组的最大值

    public int maxsumofSubarray (int[] arr) {
        // write code here
        int max=arr[0];
        int dp=arr[0];

        int len=arr.length;
        for(int i=1;i<len;i++){
            dp=Math.max(arr[i],dp+arr[i]);
            max=Math.max(dp,max);

        }
        return max;
    }