Solution by DasongLi


  • 1
    D

    Approach #1 Brute Force [Time Limit Exceeded]

    Intuition

    Check all the contiguous subarray one by one to find the maxinum.

    Algorithm

    In first loop, i represents the position where one subarray begins. And in second loop, j represents the postion where this subarray ends. In this way, we can check all the subarrays.

    c++

    class Solution {
    public:
            int maxSubArray(vector<int>& nums) {
                int i,j,k,l; i = 0;
                int max1=INT_MIN, max2=INT_MIN;
                for (i=0;i<nums.size();i++) {
                    int sum = 0;
                    for (j=i;j<nums.size();j++) {
                        sum = sum+nums[j];
                        if (sum>max2) max2 = sum;
                    }
                }
                return max2;
            }
    }
    

    Complexity Analysis

    • Time complexity : )$$O(n^2)$$.
      This program uses two loops to check all the subarrays. so the time complexity is $$O(n^2)$$.

    • Space complexity : $$O(1)$$.
      . This program stores the biggest data in array. so the space complexity is $$O(1)$$.


    Approach #2 Dividing and Conquering [Accepted]

    Intuition

    We need to use another method to decrease time. First I think out this method --- Dividing and Conquering

    Algorithm

    for mid position of one subarray whose range is [begin, end] , I consider the following three conditions.

    • 1.the left subarray whose range is [begin, mid] (Suppose the target subarray is on the left part)
    • 2.the right subarray whose range is [mid, end] (Suppose the target subarray is on the right part)
    • 3.the best result contains mid. I traverse the array by two directions. find the best result.

    I compare these three conditions and choose the biggest result.

    Another Point
    if all the elements' values are less than or equal 0, I select the biggest value as the final result.

    c++

    class Solution {
    private:
        int maxm(int a, int b, int c) {
            return max(max(a,b),c);
        }
        int search(vector<int>& nums,int begin,int end) {
            if (begin>end) return 0;
            if (begin == end) return max(nums[begin],0);
            if (end-begin==1) return maxm(nums[begin],nums[end],nums[begin]+nums[end]);
            int mid = (begin+end)/2,sum1=0,sum2=0,max1=0,max2=0;
            for (int i=mid+1;i<=end;i++) {
                sum1 = sum1 + nums[i];
                if (sum1>max1) max1 = sum1;
            }
            for (int i=mid-1;i>=begin;i--) {
                sum2 = sum2 + nums[i];
                if (sum2>max2) max2 = sum2;
            }
            
            return maxm(search(nums,begin,mid),search(nums,mid,end),nums[mid]+max2+max1);
        }
    public:
        int maxSubArray(vector<int>& nums) {
            int i,j,k,l; i = 0;
            int max1=INT_MIN, max2=INT_MIN;
            for (i=0;i<nums.size();i++) {
                if (nums[i]>max2) max2 = nums[i];
            }
            if (max2<=0) return max2;
            return search(nums,0,nums.size()-1);
        }
    }
    

    Complexity Analysis

    • Time complexity : $$O(n*log n)$$.
      This program use recursive method to achieve Dividing and Conquering. At one recursive time, the time complexity for checking the third condition is $$O(n)$$.

    • Space complexity : $$O(1)$$.
      . the space complexity is $$O(1)$$.


    Approach #3 Dynamic Programming [Accepted]

    Intuition

    The $$O(n*log n)$$ is also big, we need to optimize the program. The key is Dynamic Programming.

    Algorithm
    The state transition formula is sum[i] = max(sum[i-1]+a[i],a[i]). sum[i] means the sum which accumulates values from some place and ends at i. After one loop, I get the biggest result for subarray which ends at i.

    Note
    Similar to Approach #2, if all the elements' values are less than or equal 0, I select the biggest value as the final result.
    c++

    class Solution {
    public:
        int maxSubArray(vector<int>& nums) {
            int i,j,k,l; i = 0;
            int max1=INT_MIN, max2=INT_MIN;
            for (i=0;i<nums.size();i++) {
                if (nums[i]>max2) max2 = nums[i];
            }
            if (max2<=0) return max2;
            vector<int> res(nums.size(),0);
            if (nums.size()==1) return nums[0];
            for (i=0;i<nums.size();i++) {
                if (nums[i]>max2) max2 = nums[i];
            }
            if (max2<=0) return max2;
            res[0] = max1 = max(nums[0],0);
            for (i=1;i<nums.size();i++) {
                if (res[i-1]+nums[i]>nums[i]) {
                    res[i] = res[i-1]+nums[i];
                } else {
                    res[i] = nums[i];
                }
            }
            for (i=1;i<nums.size();i++) {
                if (res[i]>max1) max1 = res[i]; 
            }
            return max1;
        }
    }
    

    Complexity Analysis

    • Time complexity : $$O(n)$$. We just use loop to get the best results. So the time complexity is $$O(n)$$.

    • Space complexity : $$O(1)$$.
      the space complexity is $$O(n)$$.


    Approach #4 Optimized Dynamic Programming [Accepted]

    Algorithm
    I don't use one array to store the results. I just use one variable to store the best result for all subarrays which start from anywhere and end at i .

    Note
    From my perspective, this code is easy to understand.

    c++

    class Solution {
    public:
        int maxSubArray(vector<int>& nums) {
            int i,j,k,l; i = 0;
            int max1=INT_MIN, max2=INT_MIN,sum=0;
            while (i<nums.size()) {
                sum = sum + nums[i];
                if (sum>max1) max1 = sum;
                if (sum < 0 and i<nums.size()-1) sum = 0;
                i++;
            }
            return max1;
        }
    }
    

    Complexity Analysis

    • Time complexity : $$O(n)$$. We just use one while-loop to get the best results. So the time complexity is $$O(n)$$.

    • Space complexity : $$O(1)$$.
      the space complexity is $$O(n)$$.


Log in to reply
 

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