Given an array Arr of size N containing positive integers. Find the maximum sum that can be formed which has no three consecutive elements present.
Example 1:
Input: arr[] = {1,2,3}
Output: 5
Explanation: All three element present in the array is
consecutive, hence we have to consider just two
element sum having maximum,which is 2+3 = 5
Example 2:
Input: arr[] = {3000,2000,1000,3,10}
Output: 5013
Explanation: 3000 + 2000 + 3 + 10 = 5013.
Here no three elements is consecutive in that subsequence.
Your Task:
You don't need to read input or print anything. Your task is to complete the function findMaxSum() which takes the array of integers arr and n as parameters and returns an integer denoting the answer.
Expected Time Complexity: O(N)
Expected Auxiliary Space: O(N)
Constraints:
1 ≤ N ≤ 10^{6}
1 ≤ Arr_{i} ≤ 10^{7}

见题面

见题面