C++ simple O(n) solution with DP and Divide and conquer solution


  • 0
    M
        //*******************************************
        // solution 1   using dynamics programming
        // Time complexity : O(n)
        // Space complexity : O(n)
        // save the maximum value ended in i in a array maxVal[i]
    
        int maxSubArray(vector<int>& nums) {
       
            if (nums.size() < 1)
                return INT_MIN;
            vector<int> maxVal(nums);
            int best = maxVal[0];
            
            for (int i = 1; i < maxVal.size(); ++i) {
                   if (maxVal[i - 1] > 0)
                       maxVal[i] += maxVal[i - 1];
                   best = max(maxVal[i],best);
            }
            return best;
    }
    
        //***********************************************
        // solution 2, using divide and conquer method
        // Divide array into three part: left part, right part, and crossing part
        // Time complexity: O(nlogn)
        // Space complexity: O(1)
    
    int maxSubArray(vector<int>& nums) {
            if (nums.size() < 1)
                return INT_MIN;
            return maxSubArrayHelper(nums, 0, nums.size() - 1);
            
        }
    int maxCrossSubArray(vector<int>& nums, int l, int m, int h) {
            // maximum value in the left part of midpoint (including midpoint)
            int left_part = INT_MIN;
            int right_part = INT_MIN;
            for (int i = m, sum = 0; i >= l; --i) {
                sum += nums[i];
                left_part = max(sum, left_part);
            }
            // maximum value in the right part of midpoint
            for (int i = m + 1, sum = 0; i <= h; ++i) {
                sum += nums[i];
                right_part = max(sum, right_part);
            }
            
            return left_part + right_part;
        }
        
        int maxSubArrayHelper(vector<int>& nums, int l, int h) {
            if (l == h)
                return nums[l];
            int m = (h - l) / 2 + l;
            int left_max = maxSubArrayHelper(nums, l, m);
            int right_max = maxSubArrayHelper(nums, m + 1, h);
            int cross_max = maxCrossSubArray(nums, l, m, h);
            return max(max(left_max,right_max),cross_max);
        }

Log in to reply
 

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