Title:

Given an integer array nums, find the contiguous subarray (containing at least one number) which has the largest sum and return its sum.

A subarray is a contiguous part of an array.

Given an integer array nums, find a continuous sub array with the largest sum (the sub array contains at least one element) and return its maximum sum.

Example 1:

Input: nums = [-2,1,-3,4,-1,2,1,-5,4]
Output: 6
Explanation: [4,-1,2,1] has the largest sum = 6.

Example 1:

Input: num = [- 2,1, - 3,4, - 1,2,1, - 5,4]
Output: 6
Explanation: the maximum sum of continuous subarrays [4, - 1,2,1] is 6.

Example 2:

Input: nums = [1]
Output: 1

Example 2:

Input: num = [1]
Output: 1

Example 3:

Input: nums = [5,4,-1,7,8]
Output: 23

Example 3:

Input: num = [5,4, - 1,7,8]
Output: 23

Constraints:

• 1 <= nums.length <= 3 * 1 0 4 10^4 104
• - 1 0 5 10^5 105 <= nums[i] <= 1 0 5 10^5 105

Tips:

• 1 <= nums.length <= 3 * 1 0 4 10^4 104
• - 1 0 5 10^5 105 <= nums[i] <= 1 0 5 10^5 105

Follow up:

If you have figured out the O(n) solution, try coding another solution using the divide and conquer approach, which is more subtle.

Advanced:

If you have found an O(n) solution, try writing another solution using the divide and conquer method to see which is more subtle.

Problem solving ideas:

Method 1: greedy algorithm

Greedy algorithm: make the current optimal solution, that is, the local optimal solution in a sense.

For this problem: to find the maximum sub order sum, when the array num = [- 2,1, - 3,4, - 1,2,1, - 5,4] calculates the sub order sum, it must start from 1 (i.e. the previous sub order and discard), and when the sub order sum is less than 0, it abandons the current sub order and starts from the next element.

python code

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        pre = -float('inf')
        subMax = 0
        for i in range(len(nums)):
            subMax += nums[i]
            if subMax > pre:
                pre = subMax
            if subMax <= 0:
                subMax = 0
        return pre

Java code

class Solution {
    public int maxSubArray(int[] nums) {
        if (nums.length == 1){
            return nums[0];
        }
        int pre = Integer.MIN_VALUE;
        int subMax = 0;
        for (int i = 0; i < nums.length; i++){
            subMax += nums[i];
            pre = Math.max(pre, subMax);
            if (subMax <= 0){
                subMax = 0; 
            }
        }
       return pre;
    }
}

C + + code

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int pre = INT_MIN;
        int subMax = 0;
        for (int i = 0; i < nums.size(); i++) {
            subMax += nums[i];
            if (subMax > pre) { 
                pre = subMax;
            }
            if (subMax <= 0) { // The core of greed
                subMax = 0; 
            }
        }
        return pre;
    }
};

Complexity analysis

• Time complexity: O(n), where n is the length of array nums.
• Space complexity: O(1), only constant space is needed to store variables.

Method 2: dynamic programming

Suppose the length of the num array is n and the subscript is from 0 to n-1.

We use a(i) to represent the "maximum sum of continuous subarrays" ending with the ith number, that is, the formula for finding the maximum value is expressed as:
a ( i ) = m a x a ( i ) 0 ≤ i ≤ n − 1 a(i)=max {a(i)}_{0≤i≤n−1} a(i)=maxa(i)0≤i≤n−1​

We need to find a(i) at each position, and then compare whether the sum of the previous sub order is greater than 0. When it is greater than 0, the sum of the current sub order plus the sum of the previous sub order. So we need to compare n u m s [ i ] n u m s ( i − 1 ) {nums}[i]nums(i−1) nums[i]nums(i − 1) and
n u m s [ i ] nums[i] The size of nums[i], so the following dynamic programming transfer equation is obtained:

a ( i ) = m a x { n u m s ( i − 1 ) + n u m s [ i ] , n u m s [ i ] } a(i)=max\{{nums(i−1)+nums[i],nums[i]}\} a(i)=max{nums(i−1)+nums[i],nums[i]}

python code

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        subMax = 0
        pre = nums[0]
        for x in nums:
            subMax = max(subMax + x, x)
            pre = max(pre, subMax)
        return pre

Java code

class Solution {
    public int maxSubArray(int[] nums) {
        int subMax = 0;
        int pre = nums[0];
        for (int x : nums){
            subMax = Math.max(subMax + x, x);
            pre = Math.max(pre, subMax);
        }
        return pre;
    }
}   

C + + code

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int pre = 0, subMax = nums[0]; 
        for (const auto &x: nums) {
            pre = max(pre + x, x);
            subMax = max(subMax, pre);
        }
        return maxAns;
    }
};

Complexity analysis

• Time complexity: O(n), where n is the length of array nums.
• Space complexity: O(1), only constant space is needed to store variables.

Method 3: divide and treat

Now, according to the idea of divide and conquer algorithm, the maximum continuous suborder and mSum on the demand interval [l, r] should be solved by dividing [l, r] into left interval [l, m] and right interval R: [m+ 1, r].

In an interval [l,r], we use the following four:

• lSum represents the maximum suborder sum with L as the left endpoint in [l,r]
• rSum represents the maximum suborder sum with r as the right endpoint in [l,r]
• mSum represents the maximum suborder sum in [l,r]
• iSum represents the interval sum of [l,r]

How to get the information of [l,r] by merging the information of the left and right sub intervals?

• The iSum of interval [l,r] is equal to the iSum of the left sub interval + the iSum of the right sub interval
• There are two possibilities for the lSum of [l,r]. It is either equal to the lSum of the left subinterval or equal to the iSum of the left subinterval + the lSum of the right subinterval, whichever is greater.
• rSum of [l,r], similarly, it is either equal to}rSum of the right subinterval, or equal to iSum of the right subinterval plus rSum of the left subinterval, whichever is greater.
• The mSum of [l,r] may be the sum of the mSum of the left subinterval, the mSum of the right subinterval, and the sum of the rSum of the left subinterval and the lSum of the right subinterval, whichever is greater.

python code

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        max_num = self.findMax(nums)
        return max_num
    def findMax(self, nums: List[int]) -> int:
        if len(nums) == 1:
            return nums[0]
        else:
            max_left = self.findMax(nums[0:len(nums) // 2])
            max_right = self.findMax(nums[len(nums) // 2:len(nums)])
        max_l = nums[len(nums) // 2 - 1]
        count = 0
        for i in range(len(nums) // 2 - 1, -1, -1):
            count += nums[i]
            max_l = max(count, max_l)
        max_r = nums[len(nums) // 2]
        count = 0
        for i in range(len(nums) // 2, len(nums)):
            count += nums[i]
            max_r = max(count, max_r)
        return max(max_right, max_left, max_l + max_r)

Java code

class Solution {
    public class Status {
        public int lSum, rSum, mSum, iSum;

        public Status(int lSum, int rSum, int mSum, int iSum) {
            this.lSum = lSum;
            this.rSum = rSum;
            this.mSum = mSum;
            this.iSum = iSum;
        }
    }

    public int maxSubArray(int[] nums) {
        return getInfo(nums, 0, nums.length - 1).mSum;
    }

    public Status getInfo(int[] a, int l, int r) {
        if (l == r) {
            return new Status(a[l], a[l], a[l], a[l]);
        }
        int m = (l + r) >> 1;
        Status lSub = getInfo(a, l, m);
        Status rSub = getInfo(a, m + 1, r);
        return pushUp(lSub, rSub);
    }

    public Status pushUp(Status l, Status r) {
        int iSum = l.iSum + r.iSum;
        int lSum = Math.max(l.lSum, l.iSum + r.lSum);
        int rSum = Math.max(r.rSum, r.iSum + l.rSum);
        int mSum = Math.max(Math.max(l.mSum, r.mSum), l.rSum + r.lSum);
        return new Status(lSum, rSum, mSum, iSum);
    }
}

C + + code

class Solution {
public:
    struct Status {
        int lSum, rSum, mSum, iSum;
    };

    Status pushUp(Status l, Status r) {
        int iSum = l.iSum + r.iSum;
        int lSum = max(l.lSum, l.iSum + r.lSum);
        int rSum = max(r.rSum, r.iSum + l.rSum);
        int mSum = max(max(l.mSum, r.mSum), l.rSum + r.lSum);
        return (Status) {lSum, rSum, mSum, iSum};
    };

    Status get(vector<int> &a, int l, int r) {
        if (l == r) {
            return (Status) {a[l], a[l], a[l], a[l]};
        }
        int m = (l + r) >> 1;
        Status lSub = get(a, l, m);
        Status rSub = get(a, m + 1, r);
        return pushUp(lSub, rSub);
    }

    int maxSubArray(vector<int>& nums) {
        return get(nums, 0, nums.size() - 1).mSum;
    }
};

Complexity analysis

• Time complexity: o( n l o g n nlogn nlogn), where the depth of recursion is logarithmic, and each layer needs to traverse the array.
• Space complexity: o( l o g n logn logn), a constant variable is required, and the space used depends on the depth of the recursive stack.