day9.cpp

#include <iostream>
#include <vector>

#include <algorithm>

using namespace std;

'''
Given an array of numbers N and an integer k, your task is to split N into k partitions such that
 the maximum sum of any partition is minimized. Return this sum.

For example, given N = [5, 1, 2, 7, 3, 4] and k = 3, you should return 8, since the optimal partition is [5, 1, 2], [7], [3, 4].
'''
int solution(vector <int> arr, int k){

    sort(arr.begin(), arr.end());

    for (int i=0;i<arr.size();i++){  
        cout<<arr[arr.size()-1-i]<<" ";
    }
    cout<<endl;
    
    int sum [k];

    for (int i=0;i<k;i++){
        sum[i]=0;
    }
    int min_index = 0;
    int min_sum = 0;

    for (int i=0;i<arr.size();i++){  

        for (int j=0;j<k;j++){
            if(sum[j] <= min_sum){
                min_sum = sum[j];
                min_index = j;
            }
        }
        sum[min_index]+=arr[arr.size()-1-i];
        min_sum = sum[min_index];


    }

    int max = 0;
    for (int i=0;i<k;i++){
        if(sum[i]>max){
            max = sum[i];
            
        }
        cout<< sum[i]<<" ";
    }
    cout<<endl;
    return max;
}

int main(){

    vector <int> arr = {5,1,2,7,3,4};
    int k = 3;
    cout << solution(arr, k) << endl;
    return 0;
}