Problem Statement

Given an array of positive numbers, find the maximum sum of a subsequence with the constraint that no 2 numbers in the sequence should be adjacent in the array. So 3 2 7 10 should return 13 (sum of 3 and 10) or 3 2 5 10 7 should return 15 (sum of 3, 5 and 7).Answer the question in most efficient way.Examples :

Input : arr[] = {5, 5, 10, 100, 10, 5}
Output : 110

Input : arr[] = {1, 2, 3}
Output : 4

Input : arr[] = {1, 20, 3}
Output : 20

Problem Link

Maximum sum such that no two elements are adjacent - GeeksforGeeks

Reference Video

https://www.youtube.com/watch?v=VT4bZV24QNo

Code

class Solution
{
    public:
    //Function to find the maximum money the thief can get.
    ll max(int a,int b)
    {
        return a>b?a:b;
    }
    ll FindMaxSum(ll arr[], ll n)
    {
       int excl = 0,incl = arr[0];
       
       for(int i=1;i<n;i++)
       {
           int excl_temp = max(excl,incl);
           incl = excl + arr[i];
           excl = excl_temp;
       }
       return max(incl,excl);
    }
};

Time complexity O(n)

Space complexity O(1)