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

https://www.codechef.com/viewsolution/47276118

Logic is as follows

if K = 1, its a maximum subarray problem so done with kadane’s algorithm

else

I have used a 3d dp[n][k][2] 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][0] 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][0], dp[n][k][1])

to calculate this I have written some code and I think I covered all conditions possible.

Any help is appreciated.

Thanks!!

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.

Test case

```
1
5 5
-1 -2 -3 -4 -5
```

Thanks for helping.

Much appreciated.

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.

2 Likes

If there are -ve values than initialising with -inf if not then 0 , if you don’t know then -inf

1 Like

can u please share ur top down approach ?