index
| submit
| rank
| book

## max-subarray – Maximum subarray

Write a program that solves the maximum subarray problem.
In a given array or list,
your program must find the maximum sum of
a non-empty contiguous selection of elements.

For example,
in the list 1, -2, 3, 4, -5, 6, -7,
the maximum sum is achieved by selecting elements 3 through 6 yielding the sum of 8.
In the list -14, 32, -30, 60, -360,
the maximum sum is achieved by selecting elements 32, -30 and 60 yielding the sum of 62.

### Input and Output

Each line of input will contain several integers separated by space.
There will be no more than 1000 integers per line
and their absolute value shall not exceed 999.

Each line of output should contain
the maximum sum of a contiguous selection of elements.

#### Example input

```
-1 0 9 -8
1 -2 3 4 -5 6 -7
-14 32 -30 60 -360
```

### Scoring

- 1/6: works for the above example but produces output in an incorrect format
- 2/6: works for the above example and produces output in the correct format
- 4/6: works for other test cases
- 5/6: has good performance
- 6/6: works for edge cases

### Hints

Selected sub-arrays must be contiguous, i.e., without gaps.
Selected sub-arrays must be non-empty, i.e., with at least one element.

try first: cash

try next: sorting

index
| submit
| rank
| book

Copyright © 2020-2022 Rudy Matela

All rights reserved