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)