Evolve from brute force to optimal, a review of all solutions


  • 2
    1. O(n^2), try all subarrays
        int maxSubArray(vector<int>& nums) {
            int n=nums.size();
            int ma=INT_MIN;
            for(int i=0;i<n;i++) {
                int s=0;
                for(int j=i;j<n;j++) {
                    s+=nums[j];
                    ma = max(ma, s);
                }    
            }
            return ma;
        }
    
    1. O(n), dp, for a subarray, we don't have to try both ends as above. We can just try one end. The next subarray sum can be computed from the previous one using the dp relation.
        int maxSubArray(vector<int>& nums) {
            int pre =0, ma=INT_MIN;
            for(int i=0;i<nums.size();i++) {
                pre = pre>0? pre+nums[i]:nums[i];
                ma= max(ma,pre);
            }
            return ma;
        }
    
    1. O(nlogn) Naive divide and conquer. the max subarray is the max of the left, right, and the one that spans the boundary.
        int maxSubArray(vector<int>& nums) {
            return maxSubArray(0,nums.size()-1,nums);
        }
        int maxSubArray(int l, int r, vector<int>& nums) {
            if(l==r) return nums[l];
            int mid= (l+r)/2;
            int ms=maxSubArray(l,mid,nums);
            ms=max(ms,maxSubArray(mid+1,r,nums));
            int pre=0, ml=INT_MIN;
            for(int i=mid;i>=l;i--) {
                pre+=nums[i];
                ml=max(ml,pre);
            }
            pre=0;
            int mr=INT_MIN;
            for(int i=mid+1;i<=r;i++) {
                pre+=nums[i];
                mr=max(mr,pre);
            }
            return max(ms,ml+mr);
        }
    
    1. O(n) divide and conquer, the max subarray starting and ending at the boundary can be computed at the leaves and passed up. Idea is from @wyattliu
        int maxSubArray(vector<int>& nums) {
            int ml, mr, sum;
            return maxSubArray(0,nums.size()-1, ml, mr, sum, nums);
        }
        int maxSubArray(int l, int r, int& ml, int& mr, int& sum, vector<int>& nums) {
            if(l==r) return ml = mr = sum = nums[l];
            int mid= (l+r)/2, lml, lmr, lsum, rml, rmr, rsum;
            int ms=maxSubArray(l,mid,lml,lmr,lsum,nums);
            ms=max(ms,maxSubArray(mid+1,r,rml,rmr,rsum,nums));
            ml = max(lml, lsum+rml);
            mr = max(rmr, rsum+lmr);
            sum = lsum+rsum;
            return max(ms,lmr+rml);
        }
    

Log in to reply
 

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