Hey Google, play poker.

Problem Statement:

Google is testing their Google Assistant’s skill in the high risk, high reward game of poker. Sundar Pichai asks his product manager for a report on the success rates of the assistant. The product manager then turns to you and asks you to complete a task. You are given an integer array A of length N. Find the contiguous subarray of the array which has the largest sum.

Constraints:

• -10⁹ ≤ A_i ≤ 10⁹

Subtask 1: 20 points

• 1 ≤ N ≤ 100

Subtask 2: 30 points

• 1 ≤ N ≤ 1000

Subtask 3: 50 points

• 1 ≤ N ≤ 10⁵

Input Format:

• The first line contains a single integer N
• The second line contains N space separated integers denoting the elements of array A

Output Format:

• Output the sum of the contiguous subarray with the largest sum

Sample input:

6 5 -3 -2 3 5 -4 

Sample output:

8