'''
[easy]
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.
Follow up:

If you have figured out the O(n) solution, try coding another solution using the divide and conquer approach, which is more subtle.

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/maximum-subarray
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
'''

# version 1: O(n)
class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        f=[]+nums
        for i in range(1,len(nums)):
            f[i]=max(f[i-1]+nums[i],f[i])
        return max(f)


# version 2: O(nlogN)