Max Sum K-Partition

#1

code not working
code:
#include<bits/stdc++.h>
using namespace std;
int main(){
int n,k;
cin>>n>>k;
int arr[n];
for(int i=0;i<n;i++){
cin>>arr[i];
}
int ans[n];
for(int i=0;i<min(n,k);i++){
ans[i]=arr[i];
}
for(int j=1;j<ceil(float(n)/float(k));j++){

    for(int i=0;i<k;i++){
        int current_index=k*j + i;

        if (current_index>=n){
            break;
        }
        int val=arr[current_index];
        int m_val=0;
        int m=0;
        for(int p=0;p<k;p++){
            int c_i=(j-1)*k + p;
            if (i!=p && val+ans[c_i]>m_val){
                m_val=val+ans[c_i];
            }
            if(arr[c_i]>m){
                m=ans[c_i];
            }
        }
        ans[current_index]=max(m,m_val);
    }
}
int m=0;
for(int i=(ceil(float(n)/float(k))-1)*k;i<n;i++){
    if (ans[i]>m){
        m=ans[i];
    }
}
cout<<m<<endl;

return 0;

}

#2

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