
#Given an integer array nums, find the contiguous subarray (containing at 
#least one number) which has the largest sum and return its sum.

#Example:

#Input: [-2,1,-3,4,-1,2,1,-5,4],
#Output: 6
#Explanation: [4,-1,2,1] has the largest sum = 6.

#dynamics programming:
def maxSubArray(nums) -> int:
    if len(nums)==0:
        return 0
    dp=[0 for _ in range(len(nums))]
    dp[0]=nums[0]
    for i in range(1, len(nums)):
        dp[i]=max(dp[i-1]+ nums[i], nums[i])
    return max(dp)
maxSubArray([-2,1,-3,4,-1,2,1,-5,4])


## divide and conquer  O(n log n)
def maxCrossingSum(arr, l, m, h) : 
      
    # Include elements on left of mid. 
    sm = 0; left_sum = -10000
      
    for i in range(m, l-1, -1) : 
        sm = sm + arr[i] 
          
        if (sm > left_sum) : 
            left_sum = sm 
    # Include elements on right of mid 
    sm = 0; right_sum = -1000
    for i in range(m + 1, h + 1) : 
        sm = sm + arr[i] 
          
        if (sm > right_sum) : 
            right_sum = sm 
      
  
    # Return sum of elements on left and right of mid 
    # returning only left_sum + right_sum will fail for [-2, 1] 
    return max(left_sum + right_sum, left_sum, right_sum) 
  
  
# Returns sum of maxium sum subarray in aa[l..h] 
def maxSubArraySum(arr, l, h) : 
      
    # Base Case: Only one element 
    if (l == h) : 
        return arr[l] 
  
    # Find middle point 
    m = (l + h) // 2
  
    # Return maximum of following three possible cases 
    # a) Maximum subarray sum in left half 
    # b) Maximum subarray sum in right half 
    # c) Maximum subarray sum such that the  
    #     subarray crosses the midpoint  
    return max(maxSubArraySum(arr, l, m), 
               maxSubArraySum(arr, m+1, h), 
               maxCrossingSum(arr, l, m, h)) 

def maxSubArray(nums) -> int:
    return maxSubArraySum(nums, 0, len(nums)-1)

maxSubArray([-2,1,-3,4,-1,2,1,-5,4])