May Lunchtime - K - subarrays

help
1

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!!

2

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
3

Thanks for helping.
Much appreciated.
Did it now.

4

for K=2 there was a similar problem in codechef

. Also for K>2 can we write a top-down approach?

5

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?

6

I did the problem but it took me an hour or so that’s why asking. Thanks

7

Had you solved it ? Or do you still need help ?

8

yes

9

I have solved the problem. Thanks to you.
I was asking for the general approach to guess how to initialise dp.

2 Likes
10

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

1 Like
11

Thanks for help…

12

can u please share ur top down approach ?