Maximum Subarray

Medium

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

Constraints

1 ≤ nums.length ≤ 10^5
-10^4 ≤ nums[i] ≤ 10^4

Examples

Input

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

Output

Explanation

We need to find a contiguous subarray with the maximum possible sum. If we look at the array, the subarray: [4, -1, 2, 1] has the largest sum. 4 + (-1) + 2 + 1 = 6 So, the maximum subarray sum is 6.

Hints

💡 Hint 1

💡 Hint 2

Code

Upload

Test Result

Run your code to see results here...