1211. Maximum Subarray Sum (Kadane's — DP View)

Given an array nums, return the largest sum of any non-empty contiguous subarray, using the DP formulation of Kadane's algorithm. The input is JSON {nums}.

Input: JSON {nums}.

Output: Integer — the maximum subarray sum.

Examples

Input: {"nums":[-2,1,-3,4,-1,2,1,-5,4]}
Output: 6
Explanation: [4,-1,2,1] sums to 6.

Input: {"nums":[-1]}
Output: -1
Explanation: Single negative element.

Input: {"nums":[5,4,-1,7,8]}
Output: 23
Explanation: The whole array.

Constraints

• 1<=n<=10^5

Asked by