Given an integer array nums, find the contiguous subarray with the largest sum, and return its sum. This is a well-known DP problem that can be solved with space optimization.
nums = array of integers
maximum sum of a contiguous subarray
Example 1:
Input:
nums = [-2,1,-3,4,-1,2,1,-5,4]
Output:
6
Explanation:
The best subarray is [4,-1,2,1].
Example 2:
Input:
nums = [1]
Output:
1
Explanation:
A single element array returns that element.