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

简单动态规划
数组里每个元素都有两个状态 一个是在最大累加和子数组中，一个是不在最大累加和子数组中
那么从上一个元素到下一个元素状态之间就有下面四种转移关系如下：
1.上个元素在子数组中，本元素在
2.上个元素不在，本元素在
3.上个元素在，本元素不在
4.上个元素在，本元素也不在
定义初始状态：dp[0] = arr[0] dp[1] = 0, 代表元素在数组中和不在数组中
定义状态转移方程：
dp[1] = max(dp[0],dp[1]) 实际上就是上一元素在或不在数组中的两种状态下累加和取最大值
dp[0] = max(arr[i],dp[0]+arr[i]) 本元素是否加入数组
最终返回最后一个元素时在或不在数组中的两个状态取最大值即可

public int maxsumofSubarray (int[] arr) {
        // write code here
        int[] dp = new int[2];
        dp[0] = arr[0];
        dp[1] = 0;
        for(int i=1;i<arr.length;i++){
            dp[1] = Math.max(dp[0],dp[1]);
            dp[0] = Math.max(dp[0]+arr[i],arr[i]);
        }
        return Math.max(dp[0],dp[1]);
    }