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

解题思路：
动态数组dp[i]为下标为i处的最大累和
dp[0] = arr[0]
当dp[i-1]>0,  dp[i] = dp[i-1]+arr[i]
当dp[i-1]<=0, dp[i] = arr[i]  
#
# max sum of the subarray
# @param arr int整型一维数组 the array
# @return int整型
#
class Solution:
    def maxsumofSubarray(self , arr ):
        # write code here

        '''
        print(arr)
        t = 0
        maxsum1 = 0
        for i in arr:
            t += i
            if t<0:
                t=0
            elif t>maxsum1:
                maxsum1 = t

        n = len(arr)
        dp = [0]*n
        dp[0] = arr[0]
        for i in range(1,n):
            if dp[i-1]>0:
                dp[i] = dp[i-1]+arr[i]
            else:
                dp[i] = arr[i]
        maxsum2 = max(dp)


        n = len(arr)
        dp = [0]*n
        dp[0] = arr[0]
        for i in range(1,n):
            dp[i] = max(dp[i-1]+arr[i], arr[i])
        maxsum3 = max(dp)     
        '''

        n = len(arr)
        t_max = arr[0]
        maxsum = arr[0]
        for i in range(1,n):
            t_max = max(t_max+arr[i], arr[i])
            if t_max > maxsum:
                maxsum = t_max

        #print(maxsum1)
        #print(maxsum2)
        return maxsum