Any Editorial for EOSUBSEQ

editorial
,
1

I was trying out this question from ICPC Asia : Gwalior-Pune Onsite replay 2018, Even Odd Sub-sequence (EOSUBSEQ).

It looks like a straight up DP question, it would be great if someone could point out an editorial or maybe any resource which could help in understanding this question better?

2

I just divided the problem in 2 parts - odd and even. Just make a dp1[] and dp2[]table for odd and even -
I will explain in short about the odd part, do similarly for even part then -
dp1[0]= arr[i}%2==1 ? arr[i] : 0 (If first element is odd, put dp1[0] equal to that element ,else dp1[0]=0)
Then just use this formula-
dp1[i]=max(dp1[i-1], dp1[i-(k+1)]+arr[i])

  1. If((i-(k+1))<0), take that term as 0
  2. If arr[i] is even, take it as 0
    Take some sequence and try it out yourself

The answer is just dp1[n-1] + dp2[n-1]

3

this makes sense! thank you!