7 months ago

Kunal Kumar • 0

Amritsar

Solution using DP

int split(vector<int> &v, int start, int end, int m, vector<vector<int>> &dp)

{

    if ((end - start + 1) < m)

        return INT_MIN;

    if ((end - start + 1) < 2 * m)

        return v[end] - v[start];

    if (dp[start][end] != -1)

    {

        return dp[start][end];

    }

    int ans = INT_MAX;

    for (int i = start + m - 1; i < end - m + 1; i++)

    {

        int l = split(v, start, i, m, dp);

        int r = split(v, i + 1, end, m, dp);

        if (l == INT_MIN || r == INT_MIN)

        {

            ans = max(ans, v[end] - v[start]);

        }

        else

        {

            ans = min(ans, max(l, r));

        }

    }

    return dp[start][end] = ans;

}

int fun(vector<int> &nums, int m)

{

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

    int n = nums.size();

    vector<vector<int>> dp(n + 1, vector<int>(n + 1, -1));

    if (n < 2 * m)

    {

        return nums[nums.size() - 1] - nums[0];

    }

    int ans = INT_MAX;

    for (int i = m - 1; i < n - m; i++)

    {

        int l = split(nums, 0, i, m, dp);

        int r = split(nums, i + 1, n - 1, m, dp);

        ans = min(ans, max(l, r));

    }

    return ans;

}

int main()

{

    // vector<int> a = {5, 11, 13, 4, 12};

    vector<int> a ={93, 32, 88, 9, 58, 15};

    cout <<fun(a, 3);

}