The problem is asking us to partition the array into multiple subarrays, such that the sum of each subarray is positive.

Consider a partitioning a[1...p1], a[p1 + 1... p2], a[p2 + 1 ... p3], etc. where p[i] is the last index of the ith subarray.

Clearly, we can rewrite this using prefix sums,

pref[p1] - pref[0], pref[p2] - pref[p1], pref[p3] - pref[p2] , etc.

clearly, all of these terms need to be positive, meaning that pref[p(i)] > pref[p(i - 1)]

This means we need to find and restore an increasing subsequence of length k on an array of prefix sums, which can be done with a simple modification to the normal LIS

Hope this helps, :p