Question
Max 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
User Task:
Since this will be a functional problem, you don't have to take input. You just have to complete the function maxSum() that takes integer n and array arr as its input parameters and return the maximum sum adhering to the given condition.
Custom Input:
First line contains a single integer n representing the size of the array.
Next line contains n space separated integers as input representing the array arr.
Constraints
1 ≤ n ≤ 105
1 ≤ arr[i] ≤ 106
Since this will be a functional problem, you don't have to take input. You just have to complete the function maxSum() that takes integer n and array arr as its input parameters and return the maximum sum adhering to the given condition.
Custom Input:
First line contains a single integer n representing the size of the array.
Next line contains n space separated integers as input representing the array arr.
Constraints
1 ≤ n ≤ 105
1 ≤ arr[i] ≤ 106
Output
Return 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.