C++ O(n) without DP

interview-questions
Tags: #<Tag:0x00007f242d96f908>

#1

int Solution::adjacent(vector<vector > &arr){
int n=arr[0].size();
vector temp(n);
for(int i=0;i<n;i++){
temp[i]=max(arr[0][i],arr[1][i]);
}
int curen=temp[0],curex=0,preen=temp[0],preex=0;
int ans=temp[0];
for(int i=1;i<n;i++){
curen=preex+temp[i];
curex=preen;
ans=max(ans,max(curen,curex));
preen=max(curen,preen);
preex=max(curex,preex);
}
return ans;

}


#2

This still is dp. Also, please don’t post solutions here.