Loading...
No output yet. Run your code to see results.
Maximum Subarray
#048
medium
array
algorithm
dynamic-programming
Description
Given an integer array nums, find the contiguous subarray (containing at least one number) which has the largest sum and return its sum.
A subarray is a contiguous part of an array.
Example:
-
Input:
nums = [-2,1,-3,4,-1,2,1,-5,4] -
Output:
6(the subarray[4,-1,2,1]has the largest sum) -
Input:
nums = [1] -
Output:
1
Instructions
- Return the maximum sum (a single integer)
- Use Kadane's algorithm for O(n) time complexity
- At least one element must be included in the subarray