#
# max sum of the subarray
# @param arr int整型一维数组 the array
# @return int整型
#
class Solution:
    def maxsumofSubarray(self , arr ):
        # write code here
        n = len(arr)
#         dp = [0 for _ in range(n+1)]
        dp = 0
        res = 0
        for i in range(1, n+1):
            dp = max(arr[i-1], dp+arr[i-1])
            res = max(res, dp)
        return res