Hariharan's Troops


Submit solution

Points: 30 (partial)
Time limit: 1.0s
Memory limit: 12M

Authors:
Problem type
Allowed languages
C++, Python

TASK

Hariharan is playing a game of Clash Of Clans. He needs to select troops for his army. All the soldiers are standing in a line. There is a superstition for Hariharan that he should pick only the soldiers who are standing consecutivetly .He cannot pick 1st at and omit 2nd soldier and pick 3rd soldier. But he can pick all 1,2,3 soldiers. Each soldier has a strength which might be negative. Help Hariharan to maximize the total strength of soldiers he is going to choose. You are given an array of strengths of soldiers. Note: There can be cases where Hariharan doesn't wish to choose anyone.

Input Format

First line of input will be length of the array
Next n numbers are followed by strengths of each soldier

Output Format

output a single integer, the maximum sum of strengths of troops that Hariharan can get

Sample Input

6
1 -1 2 -3 4 5

Sample Output

9

Comments

There are no comments at the moment.