Maximum Subarray Sum (Kadane's Algorithm)

Given an integer array, find the contiguous subarray (containing at least one number) which has the largest sum and return its sum.

Input Format

nums = array of integers

Output Format

Maximum sum of a contiguous subarray

Constraints

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

Examples

Example 1:

Input:

nums = [-2,1,-3,4,-1,2,1,-5,4]

Output:

6

Explanation:

Subarray [4,-1,2,1] has sum 6.

Loading...
Maximum Subarray Sum (Kadane's Algorithm)