Advertisement
prakharvk

maximum sum sbsequence such that no two are adjacent(O(n) solution, optimal)

Jun 22nd, 2019
111
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 0.52 KB | None | 0 0
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. int maxSum(vector<int>&v){
  4.     int n=v.size();
  5.     if(n==0)
  6.         return 0;
  7.     int incl=v[0];
  8.     int excl=0;
  9.     for(int i=1;i<n;i++){
  10.         int temp=excl;
  11.         excl=max(incl,excl);
  12.         incl=temp+v[i];
  13.        
  14.     }
  15.    
  16.     return max(incl,excl);
  17.    
  18. }
  19.  
  20. int main(){
  21.     int t;
  22.     cin>>t;
  23.     while(t--){
  24.         int n;
  25.         cin>>n;
  26.         vector<int>v(n);
  27.         for(int i=0;i<n;i++){
  28.             cin>>v[i];
  29.         }
  30.         cout<<maxSum(v)<<endl;
  31.     }
  32.     return 0;
  33. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement