Split Array Largest Sum Solutions in C++

// Source : https://leetcode.com/problems/split-array-largest-sum/
// Author : Hao Chen
// Date   : 2016-11-13



class Solution {
public:
    // Idea
    //   1) The max of the result is the sum of the whole array.
    //   2) The min of the result is the max num among the array.
    //   3) Then, we use Binary Search to find the resullt between the `min` and  the `max`
    
    int splitArray(vector<int>& nums, int m) {
        int min = 0, max = 0;
        for (int n : nums) {
            min = std::max(min, n);
            max += n;
        }
        while (min < max) {
            int mid = min + (max - min) / 2;
            if (hasSmallerSum(nums, m, mid)) max = mid;
            else min = mid + 1;
        }
        return min;
    }
    
    
    // Using a specific `sum` to check wheter we can get `smaller sum`
    // The idea here as below:
    //   find all of possible `sub array` whose sum greater than `sum`
    //   1) if the number of `sub array` >  m, whcih means the actual result is greater than `sum`
    //   2) if the number of `sub array` <= m, whcih means we can have `smaller sum`
    //
    bool hasSmallerSum(vector<int>& nums, int m, int sum) {
        int cnt = 1, curSum = 0;
        for (int n : nums) {
            curSum += n;
            if (curSum > sum) {
                curSum = n;
                cnt++;
                if (cnt > m) return false;
            }
        }
        return true;
    }
};

/// Source : https://leetcode.com/problems/split-array-largest-sum/
/// Author : liuyubobobo
/// Time   : 2020-05-11

#include <iostream>
#include <vector>
#include <numeric>

using namespace std;


/// Memory Search
/// Time Complexity: O(n * n * m)
/// Space Complexity: O(n * m)
class Solution {

private:
    int n;

public:
    int splitArray(vector<int>& nums, int m) {

        n = nums.size();
        vector<long long> pre(n + 1, 0);
        for(int i = 0; i < n; i ++)
            pre[i + 1] = pre[i] + nums[i];

        vector<vector<int>> dp(m, vector<int>(n, -1));
        return dfs(nums, m - 1, 0, pre, dp);
    }

private:
    int dfs(const vector<int>& nums, int m, int start,
            const vector<long long>& pre, vector<vector<int>>& dp){

        if(dp[m][start] != -1) return dp[m][start];
        if(m == 0) return dp[m][start] = pre[n] - pre[start];

        int res = INT_MAX;
        for(int i = start; i + m < n; i ++)
            res =min(res, max((int)(pre[i + 1] - pre[start]), dfs(nums, m - 1, i + 1, pre, dp)));
        return dp[m][start] = res;
    }
};


int main() {

    vector<int> nums = {7, 2, 5, 10, 8};
    cout << Solution().splitArray(nums, 2) << endl;
    // 18

    return 0;
}

/// Source : https://leetcode.com/problems/split-array-largest-sum/
/// Author : liuyubobobo
/// Time   : 2020-05-11

#include <iostream>
#include <vector>
#include <numeric>

using namespace std;


/// Dynamic Programming
/// Time Complexity: O(n * n * m)
/// Space Complexity: O(n * m)
class Solution {

public:
    int splitArray(vector<int>& nums, int m) {

        int n = nums.size();
        vector<long long> pre(n + 1, 0);
        for(int i = 0; i < n; i ++)
            pre[i + 1] = pre[i] + nums[i];

        vector<vector<int>> dp(m, vector<int>(n, INT_MAX));
        for(int start = 0; start < n; start ++)
            dp[0][start] = pre[n] - pre[start];

        for(int k = 1; k < m; k ++)
            for(int start = 0; start < n; start ++)
                for(int i = start; i + k < n; i ++)
                    dp[k][start] = min(dp[k][start], max((int)(pre[i + 1] - pre[start]), dp[k - 1][i + 1]));
        return dp[m - 1][0];
    }
};


int main() {

    vector<int> nums = {7, 2, 5, 10, 8};
    cout << Solution().splitArray(nums, 2) << endl;
    // 18

    return 0;
}

/// Source : https://leetcode.com/problems/split-array-largest-sum/
/// Author : liuyubobobo
/// Time   : 2020-05-11

#include <iostream>
#include <vector>
#include <numeric>

using namespace std;


/// Dynamic Programming with Space Optimization
/// Time Complexity: O(n * n * m)
/// Space Complexity: O(n)
class Solution {

public:
    int splitArray(vector<int>& nums, int m) {

        int n = nums.size();
        vector<long long> pre(n + 1, 0);
        for(int i = 0; i < n; i ++)
            pre[i + 1] = pre[i] + nums[i];

        vector<int> dp(n);
        for(int start = 0; start < n; start ++)
            dp[start] = pre[n] - pre[start];

        for(int k = 1; k < m; k ++){
            vector<int> tdp(n, INT_MAX);
            for(int start = 0; start < n; start ++)
                for(int i = start; i + k < n; i ++)
                    tdp[start] = min(tdp[start], max((int)(pre[i + 1] - pre[start]), dp[i + 1]));
            dp = tdp;
        }
        return dp[0];
    }
};


int main() {

    vector<int> nums = {7, 2, 5, 10, 8};
    cout << Solution().splitArray(nums, 2) << endl;
    // 18

    return 0;
}

/// Source : https://leetcode.com/problems/split-array-largest-sum/
/// Author : liuyubobobo
/// Time   : 2020-05-11

#include <iostream>
#include <vector>
#include <numeric>

using namespace std;


/// Binary Search + Greedy
/// Time Complexity: O(nlog(sum))
/// Space Complexity: O(n)
class Solution {

public:
    int splitArray(vector<int>& nums, int m) {

        long long l = 1ll, r = 0ll;
        for(int num: nums) r += num;

        while(l < r){
            long long mid = (l + r) / 2;
            if(ok(nums, m, mid)) r = mid;
            else l = mid + 1;
        }
        return l;
    }

private:
    bool ok(const vector<int>& nums, int m, long long len){

        if(*max_element(nums.begin(), nums.end()) > len) return false;

        int res = 1;
        long long cur = 0ll;
        for(int e: nums){
            if(cur + e > len){
                res ++;
                cur = e;
            }
            else cur += e;
        }
        return res <= m;
    }
};


int main() {

    vector<int> nums1 = {7, 2, 5, 10, 8};
    cout << Solution().splitArray(nums1, 2) << endl;
    // 18

    vector<int> nums2 = {1,2147483647};
    cout << Solution().splitArray(nums2, 2) << endl;
    // 2147483647

    return 0;
}