Back

Maximum Subarray Medium

Arrays Dynamic Programming 2.0s 256MB 0 solved

Problem Statement

Given an integer array `nums`, find the subarray with the largest sum, and return its sum. A subarray is a contiguous non-empty sequence of elements within an array.

Input Format

The first line contains an integer `n` (the size of the array). The second line contains `n` space-separated integers representing the array.

Output Format

Print a single integer representing the maximum subarray sum.

Constraints

  • 1 <= nums.length <= 10^5
  • -10^4 <= nums[i] <= 10^4

Examples

Example 1
Input
9 -2 1 -3 4 -1 2 1 -5 4
Output
6
Explanation: The subarray [4,-1,2,1] has the largest sum 6.
Example 2
Input
1 1
Output
1
Explanation: Single element array.
Example 3
Input
5 5 4 -1 7 8
Output
23
Explanation: The entire array has the maximum sum.

Your Submissions

No submissions yet