Maximum Subarray

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

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.

Example 1

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

from typing import List

def max_sub_array(nums: List[int]) -> int:
    new_array = [i for i in nums]
    for i in range(1, len(new_array)):
        if nums[i - 1] > 0:
            new_array[i] += nums[i - 1]
    print(f"Old  : {nums}")
    print(f"New  : {new_array}")
    return max(new_array)

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

Old  : [-2, 1, -3, 4, -1, 2, 1, -5, 4]
New  : [-2, 1, -2, 4, 3, 2, 3, -4, 4]





4