74. Maximum Subarray (Kadane's Algorithm)

Given an integer array nums, find the subarray with the largest sum and return that sum.

A subarray is a contiguous non-empty sequence.

Input: An integer array nums of length n.

Output: Integer — maximum subarray sum.

Examples

Example 1

Input: [-2,1,-3,4,-1,2,1,-5,4]
Output: 6
Explanation: Subarray [4,-1,2,1] has sum 6. This is the maximum.

Example 2

Input: [1]
Output: 1
Explanation: Only one element. Return it.

Example 3

Input: [5,4,-1,7,8]
Output: 23
Explanation: Entire array sums to 23.