Problem Link : - https://www.codechef.com/problems/BUG2K18E

Statement : -

(Note:-Here ‘J’ is considered as ‘1’ and ‘F’ is considered as ‘0’.

A nice problem to brush up the basics of **dp** .

We are given an array **(A)** of integers containing ‘1’ and ‘0’ . We are given one more array **(B)** containing the corresponding values.

Example :-

**A** : 0 1 0 1

**B** : 1 2 4 3

We have to traverse the **given** array in such a way **so** that we can get the maximum sum of values from array ‘ **B’**

But here is the **twist** , say, we pick up a value at index ‘x’ , now if the value at index ‘x+1’ is ‘1’ we can never pick it up!

Example **(s) :-**

1 1 0

7 8 9

We have 2 ways:-

**1)7+9=16(We can’t pick up “8” )**

**2) 8+9=17 (As the next index is ‘0’)**

Final answer :- 17

Solution:-

**(This is my trick to solve hard-dp-problems on 1-d-array)**

Lets say, our array has only ‘3’ elements, then, if ;

**DP[I] MEANS THE BEST SUM WE CAN GET TILL INDEX ‘I’**

**a[i]=0;**

**and a[i-1]=0;**

**then, we can eat both the elements, so**

**dp[i]=b[i]+b[i-1];**

(lets eat both

**a[i]=0;**

**and a[i-1]=1;**

Again, first we will eat ‘1’, then ‘0’ , no restrictions!

**So:-dp[i]=b[i]+b[i-1];**

**a[i]=1;**

**and a[i-1]=(1 OR 0)**

Either we can eat up ‘1’ and sacrifice the previous element or we leave ‘1’ and stay happy with what we had previously

So,

**dp[i]=max(b[i]+dp[i-2],dp[i-1])**

**Applying the above recurrence relations to the full array solves our problem **

My implementation assumes ‘J’ as ‘ **1** ’ and ‘F’ as ‘ **0** ’

Link : - Ideone.com

For clarity : - https://www.geeksforgeeks.org/ma…