Maximum Subarray

Problem Statement

Given an array of integers nums, find the subarray with the largest sum and return the sum.

A subarray is a contiguous non-empty sequence of elements within an array.

Example 1:

Input: nums = [2,-3,4,-2,2,1,-1,4]

Output: 8

Explanation: The subarray [4,-2,2,1,-1,4] has the largest sum 8.

Example 2:

Input: nums = [-1]

Output: -1

Constraints:

• 1 <= nums.length <= 1000
• -1000 <= nums[i] <= 1000

Recommended Time and Space Complexity

You should aim for a solution with O(n) time and O(1) space, where n is the size of the input array.

Hint 1

Consider using dynamic programming to solve this problem.

Hint 2

Think about how to break the problem into smaller subproblems.

Solution

Brute Force

def max_sub_array(nums: list[int]) -> int:
    n = len(nums)
    res = nums[0]
    for i in range(n):
        cur = 0
        for j in range(i, n):
            cur += nums[j]
            res = max(res, cur)
    return res

Time complexity: O(n^2) Space complexity: O(1)