Question
Sum of non adjacent numbers
You're given an array containing n integers. You've to find the maximum sum of the elements of the array, but there must not be any adjacent element contributing to the sum.
Input
Input consists of two lines:
The first line contains an integer n : the size of the array.
The second line contains n space separated integers representing the array elements.
Constraints
1 <= n <= 105
1 <= arr[i] <= 106
The first line contains an integer n : the size of the array.
The second line contains n space separated integers representing the array elements.
Constraints
1 <= n <= 105
1 <= arr[i] <= 106
Output
Print the maximum sum adhering to the given condition.
Example
Sample Input
5
3 2 4 6 5
Sample Output
12
Explanation
take 3, 4, 5 (3 + 4 + 5 = 12).
Any other combination will lead to a lesser sum.
5
3 2 4 6 5
Sample Output
12
Explanation
take 3, 4, 5 (3 + 4 + 5 = 12).
Any other combination will lead to a lesser sum.