Maximum Subarray

Medium

arraydivide-and-conquerdynamic-programming

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

Input: one line of space-separated integers. Output: the maximum subarray sum.

Example 1

Input:

-2 1 -3 4 -1 2 1 -5 4

Output:

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

Example 2

Input:

5 4 -1 7 8

Output:

The whole array sums to 23.

Run your code against the sample tests, or Submit to run the full suite.

Medium

arraydivide-and-conquerdynamic-programming

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

Input: one line of space-separated integers. Output: the maximum subarray sum.

Example 1

Input:

-2 1 -3 4 -1 2 1 -5 4

Output:

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

Example 2

Input:

5 4 -1 7 8

Output:

The whole array sums to 23.

Run your code against the sample tests, or Submit to run the full suite.