Maximum Subarray
Medium
array
dynamic-programming
Problem Description
Given an integer array nums, find the contiguous subarray (containing at least one number) which has the largest sum and return its sum.
Input Format
First line contains n (array size)
Second line contains n integers
Output Format
The maximum sum of contiguous subarray
Constraints
1 <= nums.length <= 10^5
-10^4 <= nums[i] <= 10^4
Sample Input/Output
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.
Solution Hints
200
Points
Points
2000ms
Time Limit
Time Limit
256MB
Memory Limit
Memory Limit
Code Editor
Register to Access Code Editor
Create a free account to solve coding problems and track your progress.
Register Now