I will try to explain, inviting @codingmohan for review and optimizations possible FIRST:: Consider it as an LIS problem where your goal is to find the longest increasing subsequence so pseudo code becomes like: for i in range(n): for j in range(i): dp[i]=max(dp[i], dp[j]+1) # easy SECOND:: Now the contraint added is your j'th element should be having a property, that element at index j, and element at index i, their sum and then remainder must be having same value , say `rem`, where the previous subsequence ended at index j, with sum and then remainder, `rem` If you see closely, we just added another dimension `rem` whose value ranges from 0 to k-1(both inclusive) for i in range(n): for j in range(i): rem = (nums[i]+nums[j])%k dp[i][rem]=max(dp[i][rem], dp[j][rem]+1) # easy! BASE CASE:: just like LIS, every subsequence can start from that element itself, so for i in range(n): for ck in range(k): dp[i][ck]=1 # DONE!!! JUST PRINT THE MAX VALUE IN ENTIRE DP ARRAY!
Hey, can you also touch upon today's 3rd problem of weekly contest?
I will try to explain, inviting @codingmohan for review and optimizations possible
FIRST:: Consider it as an LIS problem where your goal is to find the longest increasing subsequence
so pseudo code becomes like:
for i in range(n):
for j in range(i):
dp[i]=max(dp[i], dp[j]+1)
# easy
SECOND:: Now the contraint added is your j'th element should be having a property, that element at index j, and element at index i, their sum and then remainder must be having same value , say `rem`, where the previous subsequence ended at index j, with sum and then remainder, `rem`
If you see closely, we just added another dimension `rem` whose value ranges from 0 to k-1(both inclusive)
for i in range(n):
for j in range(i):
rem = (nums[i]+nums[j])%k
dp[i][rem]=max(dp[i][rem], dp[j][rem]+1)
# easy!
BASE CASE:: just like LIS, every subsequence can start from that element itself, so
for i in range(n):
for ck in range(k):
dp[i][ck]=1
# DONE!!! JUST PRINT THE MAX VALUE IN ENTIRE DP ARRAY!
I think DP is not required at all.
ua-cam.com/video/V_bVlBaRh-s/v-deo.html