Hii Everyone, Hope everyone’s well.
Could somebody help me with my code.
I am getting WA for test 2 and 3
The link is
Logic is as follows
if K = 1, its a maximum subarray problem so done with kadane’s algorithm
I have used a 3d dp[n][k] with state as
n = number of elements from the left of the array (given array)
k = number of disjoint subarrays to divide into
0 if the last element is not present and 1 if last element is present
thus dp[n][k] gives the solution of n numbers into k partitions where the last element is not present in any array
thus the answer would be max(dp[n][k], dp[n][k])
to calculate this I have written some code and I think I covered all conditions possible.
Any help is appreciated.
looks like you forgot to take into account that values can be negative as well forming the subarrays.Try initialising required things with -inf rather then 0.
-1 -2 -3 -4 -5
Thanks for helping.
Did it now.
for K=2 there was a similar problem in codechef
. Also for K>2 can we write a top-down approach?
Sorry to bother once again.
But I wasn’t able to intuitively understand which values should be -inf and which values should be zero. In fact, in most dp problems I have a hard time doing that. Is there an easy way to find that?
I did the problem but it took me an hour or so that’s why asking. Thanks
Had you solved it ? Or do you still need help ?
I have solved the problem. Thanks to you.
I was asking for the general approach to guess how to initialise dp.
If there are -ve values than initialising with -inf if not then 0 , if you don’t know then -inf
can u please share ur top down approach ?