【牛客题霸题解】子数组的最大累加和问题

如果我们知道了以每个位置结尾的子数组的最大累加和，里面最大的那个结果就是整个数组的子数组的最大累加和了。
例：
arr = [1, -2, 3, 5, -2, 6, -1]
dp = [1, -1, 3, 8, 6, 12, 11]
所以arr数组中子数组的最大累加和为12。

设数组dp中，dp[i]表示以i位置结尾的最大累加和。
我们如何求出dp数组？

1. 只选arr[i]
2. 选arr[i]加上以i-1位置结尾的子数组的最大累加和

即：dp[i] = max(arr[i],dp[i-1]+arr[i])
c++

class Solution {
public:
    int maxsumofSubarray(vector<int>& arr) {
        int len = arr.size();
        vector<int> dp(len,0);
        dp[0] = arr[0];
        int res = arr[0];
        for(int i = 1 ; i < len; ++i){
            dp[i] = max(dp[i - 1] + arr[i],arr[i]);
            res = max(res,dp[i]);
        }
        return res;
    }
};

java

import java.util.*;
public class Solution {
   public int maxsumofSubarray (int[] arr) {
        int len = arr.length;
        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;
    }
}

python

class Solution:
    def maxsumofSubarray(self , arr ):
        dp = [0]*len(arr)
        dp[0] = arr[0]
        res = arr[0]
        for i in range(1,len(arr)):
            dp[i] = max(dp[i - 1] + arr[i],arr[i]);
            res = max(res,dp[i]);
        return res;

我们观察过程可以发现，其实并不用开一整个dp数组，因为我们每次用到的只是dp[i-1].所以拿一个变量存一下也能达到这样的效果。
c++

class Solution {
public:
    int maxsumofSubarray(vector<int>& arr) {
        int len = arr.size();
        int dp = arr[0];
        int res = arr[0];
        for(int i = 1 ; i < len; ++i){
            dp = max(dp + arr[i],arr[i])
            res = max(res,dp)
        }
        return res
    }
};

java

import java.util.*;
public class Solution {
   public int maxsumofSubarray (int[] arr) {
        int len = arr.length;
        int dp = arr[0];
        int res = arr[0];
        for(int i = 1 ; i < len; ++i){
            dp = Math.max(dp + arr[i],arr[i]);
            res = Math.max(res,dp);
        }
        return res;
    }
}

python

class Solution:
    def maxsumofSubarray(self , arr ):
        # write code here
        dp = [0]*len(arr)
        dp = arr[0]
        res = arr[0]
        for i in range(1,len(arr)):
            dp = max(dp + arr[i],arr[i])
            res = max(res,dp)
        return res