C++ Two Clean and Short Solutions: Binary Search & Traditional DP,


  • 0
    F
    /// O(log2(high - low)*n), where low high are defined as in the program below:
    struct Solution {
        int splitArray(vector<int>& nums, int m) {
            long long low = INT_MIN, high = 0;
            for (int n : nums)
                high += n, low = max<long long>(low, n);
            low = max(low , high / 50);
            while (low < high)
            {
                long long mid = low + (high - low) / 2;
                if (test(nums, m, mid))
                    high = mid;
                else
                    low = mid + 1;
            }
            return high;
        }
        bool test(vector<int>& nums, int m, long long bar)
        {
            int sum = 0, count = 1;
            for (int n : nums)
                if (sum + n > bar)
                {
                    sum = n;
                    count ++;
                    if (count > m)
                        return false;
                }else
                    sum += n;
            return true;
        }
    };
    
    ///O(mn^2) dp slow but short;
    struct Solution {
        int splitArray(vector<int>& nums, int m) {
            vector<long long> sums(nums.size() + 1), dp (nums.size());
            for (int i = 0; i < nums.size(); ++i)
                dp[i] = sums[i + 1] = sums[i] + nums[i];
            for (int k = 2; k <= m; ++k)
                for (int i = nums.size() - 1; i >= k - 1; --i)
                    for (int j = k - 2; j < i ; ++j)
                        dp[i]= min(dp[i], max(dp[j], sums[i + 1] - sums[j + 1] ));
            return dp[nums.size() - 1];
        }
    };
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.