Binary Search Answer + Greedy, C++ Solution


  • 0
    J

    '''

    int splitArray(vector<int>& nums, int m, int bound)
    {
        int ret = INT_MIN;
        int now = 0, cnt = 0;
        for (int x : nums)
        {
            if (x > bound) return INT_MAX;
            
            if (now + x > bound)
            {
                ret = max(ret, now);
                now = x;
                cnt++;
                if (cnt >= m) return INT_MAX;
            }
            else
            {
                now += x;
                if (now <= bound) ret = max(ret, now);
            }
        }
        
        return ret;
    }
    
    int splitArray(vector<int>& nums, int m) {
        long long sum = 0;
        for (int x : nums) sum += x;
        
        long long l = 0, r = sum;
        while (l < r)
        {
            int mid = l + (r - l) / 2;
            int t = splitArray(nums, m, mid);
            
            if (t > mid)
            {
                l = mid + 1;
            }
            else
            {
                r = mid;
            }
        }
        
        return l;
    }
    

    '''


Log in to reply
 

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