# code tpl

{%hackmd theme-dark %}

[-2,1,-3,4,-1,2,1,-5,4]

[4,-1,2,1] = 6

for max sub array sum

kadane algo

for i pos -> dp[i]

take previous or not, if previos > 0

[4,-1,2]

for dp[1], previous dp[0] is 4 > 0

num [4, -1, 2]
dp [4 , 0 ,0] curSum = 4
dp. [4, 3, 0] curSum = 3
dp. [4, 3, 5] curSum = 5
-> ans: 5

num [-1, -1, 2]
dp [-1 , 0 ,0] curSum = 0
dp [-1 , -1 ,0] curSum = 0
dp [-1 , -1 ,2] curSum = 0
-> ans: 2

class Solution(object):
    def maxSubArray(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        # [4, -1, 2]
        dp = [0]*len(nums)
        curSum = 0
        
        for i in range(len(nums)):
            dp[i] = max(num[i], curSum+num[i])
            # dp[0] -> 4
            # dp[1] -> max(-1, -1+4) -> 3
            # dp[2] -> max(2, 2+3) -> 5
            
            curSum += max(curSum+num[i], 0)
            # 4
            # 3
            # 5
        
            
        return max(dp)
        # 5
        
            
            
        

###### tags: `mock interview` `面試`