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

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)