### rum3r's blog

By rum3r, history, 3 weeks ago, What am I doing wrong in this problem?

inline void solve(){
ll n;
cin >> n;
ll a[n], b[n];
for(int i=0; i<n; ++i) {
cin >> a[i];
}
for(int i=0; i<n; ++i) {
cin >> b[i];
}
ll dp[n];
dp = a;  //selecting first person
dp = b;  //selecting second person
dp = 0;     //not selecting anyone
for(int i=1; i<n; ++i) {
dp[i] = max(dp[i-1]+a[i], max(dp[i-1]+a[i], dp[i-1]+b[i])); //for first person
dp[i] = max(dp[i-1]+b[i], max(dp[i-1]+a[i], dp[i-1]+b[i])); //for second person
dp[i] = max(dp[i-1], dp[i-1]);  //for not selecting
}
cout << max(dp[n-1], dp[n-1]) << endl;  //taking max over all..
}


PROBLEM Any help would be appreciated. Comments (4)
 » The problem is with your DP relation. In the final loop where you are filling in the states, In dp[i] you should not consider the case where you are choosing a person from the second row and similarly, In dp[i] you should not consider the case where you are choosing a person from the first row. Updated Correct Submission — Link
•  » » Thanks for giving your valuable time brother. I got it! I just want to ask, In tutorial how are they calculating the dp without array ??
•  » » » You see that the ith states of our DP (dp[i]) depend only on the (i-1)st states (dp[i-1]). So Instead of storing the values of all the previous states in an array, In the tutorial, only the values to the previous state are being stored.
•  » » » » Thanks, Buddy you're the nicest person on CF that I have ever met. Thanks for your help. :D