Max Sum K-Partition

#1

I have tried multiple test cases in this solution https://pastebin.com/x7GZwAZK please have a look , i doubt about test cases

#2

Hey the testcases are all correct. Your code is too difficult to read as you have used alot of custom #defines. If you still wonder about the testcases then take a look at this code its very simple, easy to read and again very simple :joy:
In this code I simply find a max from every k elements and add it to the sum if, that indexed max wasn’t added from the previous k elements, if not then add second max.

#include<bits/stdc++.h>
using namespace std;

int main() {
    int n, k;
    cin >> n >> k;
    vector<long> a(n);
    for(auto &i : a)
        cin >> i;
    long maxSum = 0;
    vector<long> dp = a;
    for(int i = k; i < n; i += k) {
        int max_i = i - k, smax_i = -1;
        for(int j = i - k + 1; j < i; j++) {
            if(dp[j] > dp[max_i]) {
                smax_i = max_i;
                max_i = j;
            }
            else if(smax_i == -1 or dp[j] > dp[smax_i]) {
                smax_i = j;
            }
        }
        for(int j = i; j < i + k and j < n; j++) {
			if(a[j] < 0) dp[j] = dp[max_i];
            else if(j - max_i != k) dp[j] = a[j] + dp[max_i];
            else dp[j] = a[j] + dp[smax_i];
            maxSum = max(maxSum, dp[j]);
        }
    }
    cout << maxSum;
}


Hope this helps you !

1 Like