Algorithms and Data Structures

• Status
• 1
Implementation
• 2
Bitwise operations
• 3
Prefix Sums
• 4
Sliding window / Two pointers
• 5
Modular Arithmetic
• 6
Number Theory
• 7
Binary Search
• 8
Basic Sorting
• 9
Greedy Algorithms

• # Maximum sum subarray

Given an array of `n` integers, find a contiguous subarray with the maximum sum of values.

#### Input

The first line of the input contains an integer `n` - number of elements in the array (1 ≤ n ≤ ).
The next line contains `n` integers separated by a space, that represent the elements of the array .

#### Output

The program should print a single integer - the highest possible sum of the subarrays in the given array.

#### Examples

 Input Output 9 -2 1 -3 4 -1 3 1 -4 -2 7 10 1 -2 3 4 -3 1 7 -10 -20 4 12

#### Explanation

1. -2 1 -3 `4 -1 3 1` -4 -2 → The sum of the highlighted subarray is (4 - 1 + 3 + 1) = 7
1. 1 -2 `3 4 -3 1 7` -10 -20 4 → 3 + 4 -3 + 1 + 7 = 12

Can you make this even better 😎?
It’s possible to solve this problem without any additional arrays. Can you do that?