[Leetcode刷题总结系列][Dynamic programming][Divide-and-conquer]53.Maximum Subarray

墨蓝 2022-08-21 11:45 11阅读 0赞

Find a continguous subarray within an array (containing at least one number) which has the largest sum.

找到一个数组中一个连续相加之和最大的子数组。

比如对于数组\[-1,-2,3,-1,2\]，其连续相加之和最大的子数组为\[3,-1,2\]，其和为4。

那么对于这个问题，由于考虑到如果一串连续子数组中的数字相加之和小于0，那么这一串子数组绝对不可能包含在我们想要的子数组之中，因为负数和任意数字相加都只会变小。那么我们只需要从相加之和小于0的那一刻起重新开始考虑相加的情况即可。同时使用一个 int 变量记录得到过的最大的相加之和。最终返回这个变量即可。

代码如下。

代码只需要循环一遍整个数组，所以时间复杂度为O(n)。显然，空间复杂度为O(1)。

public class Solution {
        public int maxSubArray(int[] nums) {
            /*
            Basic idea:
            Keep an integer currentsum to keep track of the current summation
            Keep another integer maxsum to keep track of the maximum summation till now
            However, if currentsum  ≤ 0; then a maximum cannot be generated under current condition (since a negative number plus any number is always less than that number),
            so we let the currentsum to be 0 (simply drop before result) under this condition and recalculate the summation again from 0 and current position.
            Otherwise, currentsum is the summation of previous currentsum and number of current position
            Then we renew the maximum summation
            */
            if (nums == null){
                return 0;
            }
            int length = nums.length;
            if (length == 1){
                return nums[0];
            }
            int currentsum = nums[0];
            int maxsum = nums[0];
            for (int i = 1; i < length; i++){
                if (currentsum >= 0){
                    currentsum += nums[i];
                }
                
                else{
                    currentsum = nums[i];
                }
                
                maxsum = maxsum > currentsum ? maxsum : currentsum;
            }
            
            return maxsum;
        }
    }

该问题还有可以用分治法(divide-and-conquer)解决。

根据该问题的内容，具有最大和的子序列存在于一下三种情况之中：

1. 该最大和子序列存在于其上一级子序列的左半部分中

2. 该最大和子序列存在于其上一级子序列的右半部分中

3. 该最大和子序列存在于其上一级子序列的中间部分（既从中间点向左右延伸的序列）

情况1和情况2可以通过迭代（recursion）解决。

情况3可以通过由中间节点开始，向左计算左半部分的和的最大值，向右计算右半部分的和的最大值，然后叠加得到。这种方法需要O(n)时间。

代码如下：

该段代码运行时间符合T(n) = 2\*T(n/2) + O(n)。根据Master Method，运行时间为O(nlogn)

public class Solution {
        public int maxSubArray(int[] nums) {
            /*
            Divide-and-conquer method.
            The maximum summation of subarray can only exists under following conditions:
            1. the maximum summation of subarray exists in left half.
            2. the maximum summation of subarray exists in right half.
            3. the maximum summation of subarray exists crossing the midpoints to left and right. 
            1 and 2 can be reached by using recursive calls to left half and right half of the subarraies. 
            Condition 3 can be found starting from the middle point to the left,
            then starting from the middle point to the right. Then adds up these two parts and return. 
            
            T(n) = 2*T(n/2) + O(n)
            this program runs in O(nlogn) time
            */
            
            int maxsum = subArray(nums, 0, nums.length-1);
            return maxsum;
        }
        
        private int subArray(int[] A, int left, int right){
            if (left == right){
                //base case
                return A[left];
            }
            int mid = left + (right-left)/2;
            int leftsum = subArray(A, left, mid); //left part of the subarray sum, condition 1
            int rightsum = subArray(A, mid+1, right); //right part of the subarray sum, condition 2
            int middlesum = midSubArray(A, left, mid, right); //cross part of the subarray sum, condition 3
            // System.out.println(leftsum);
            // System.out.println(rightsum);
            // System.out.println(middlesum);
            
            //following if condition will return middlesum if lost the "=" under the conditon of leftsum = rightsum, which may be problematic if leftsum = rightsum < middlesum.
            //for example: [-1, -1, -2, -2]
            if (leftsum >= rightsum && leftsum >= middlesum){
                return leftsum;
            }
            if (rightsum >= leftsum && rightsum >= middlesum){
                return rightsum;
            }
            return middlesum;
        }
        
        private int midSubArray(int[] A, int left, int mid, int right){
            int leftsum = Integer.MIN_VALUE;
            int rightsum = Integer.MIN_VALUE;
            int sum = 0;
            for (int i = mid; i >= left; i--){
                sum += A[i];
                if (leftsum < sum){
                    leftsum = sum;
                }
            }
            
            sum = 0;
            for (int j = mid + 1; j <= right; j++){
                sum += A[j];
                if (rightsum < sum){
                    rightsum = sum;
                }
            }
            
            return leftsum + rightsum;
        }
    }