online advertising

Saturday, October 8, 2016

LeetCode OJ - Split Array Largest Sum

Problem:

Please find the problem here.

Analysis:

This is a good problem, I spent some good time thinking about solving it.

The key idea is that finding the solution is hard, but guessing one isn't. The solution must be somewhere between $ -1 < x < sum $

If we had a way to tell if the answer is bigger of smaller than the actual solution, then we can binary search the answer.

Solution:

The question above basically turn into a feasibility question. Is it feasible to split the array such that the maximum sum is at most $ x $? We can solve this problem using a simple greedy assignment.

Walking from the beginning of the array, pick as much element as we can to fit the sum less than $ x $ constraint, and then pick the another segment, and so on. If we can get this in $ m $ segment, it is feasible, otherwise it is not.

We can use a simple exchange argument to prove that this is a valid test. If there exists a feasible split, we can always move the splitting boundary right when it is feasible, eventually, that will lead to a solution that would have been found by our greedy splitting.

Code:

#include "stdafx.h"

// https://leetcode.com/problems/split-array-largest-sum/

#include "LEET_SPLIT_ARRAY_LARGEST_SUM.h"
#include <map>
#include <algorithm>
#include <iostream>
#include <sstream>
#include <vector>
#include <string>

using namespace std;

namespace _LEET_SPLIT_ARRAY_LARGEST_SUM
{
    class Solution
    {
    public:
        int splitArray(vector<int>& nums, int m)
        {
            long long total = 0;
            for (size_t i = 0; i < nums.size(); i++)
            {
                total += nums[i];
            }

            // lo is always infeasible
            // hi is always feasible
            long long lo = -1;
            long long hi = total;
            while (lo + 1 < hi)
            {
                long long mid = lo + (hi - lo) / 2;
                long long run = 0;
                int seg = 1;
                for (size_t i = 0; i < nums.size(); i++)
                {
                    if (run + nums[i] <= mid)
                    {
                        run += nums[i];
                    }
                    else
                    {
                        if (nums[i] > mid)
                        {
                            seg = m + 1;
                            break;
                        }
                        i--;
                        seg++;
                        run = 0;
                    }
                }
                if (seg <= m)
                {
                    hi = mid;
                }
                else
                {
                    lo = mid;
                }
            }

            return hi;
        }
    };
};

using namespace _LEET_SPLIT_ARRAY_LARGEST_SUM;

int LEET_SPLIT_ARRAY_LARGEST_SUM()
{
    Solution solution;
    vector<int> input;
    input.push_back(1);
    input.push_back(2147483646);
    cout << solution.splitArray(input, 2) << endl;
    return 0;
}

No comments :

Post a Comment