LeetCode 53. Maximum Subarray（最大子数组）

leetcode.com/problems/ma…

Discuss：www.cnblogs.com/grandyang/p…

Given an integer array nums, find the contiguous subarray (containing at least one number) which has the largest sum and return its 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 2:

Input: nums = [1]
Output: 1

Example 3:

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

 

Constraints:

• 1 <= nums.length <= 3 * 104
• -105 <= nums[i] <= 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.

解法一：

这道题让求最大子数组之和，并且要用两种方法来解，分别是 O(n) 的解法，还有用分治法 Divide and Conquer Approach，这个解法的时间复杂度是 O(nlgn)，那就先来看 O(n) 的解法，定义两个变量 result 和 curSum，其中 res 保存最终要返回的结果，即最大的子数组之和，curSum 初始值为0，每遍历一个数字 num，比较 curSum + num 和 num 中的较大值存入 curSum，然后再把 result 和 curSum 中的较大值存入 result，以此类推直到遍历完整个数组，可得到最大子数组的值存在 result 中，代码如下：

class Solution {
    fun maxSubArray(nums: IntArray): Int {
        var result = Int.MIN_VALUE
        var curSum = 0

        nums.forEach {
            curSum = Math.max(curSum + it, it)
            result = Math.max(result, curSum)
        }
        return result
    }
}

解法二：

题目还要求我们用分治法 Divide and Conquer Approach 来解，这个分治法的思想就类似于二分搜索法，需要把数组一分为二，分别找出左边和右边的最大子数组之和，然后还要从中间开始向左右分别扫描，求出的最大值分别和左右两边得出的最大值相比较取最大的那一个，代码如下：

class Solution {
    fun maxSubArray(nums: IntArray): Int {
        return if (nums.isEmpty()) 0 else helper(nums, 0, nums.size - 1)
    }

    private fun helper(nums: IntArray, left: Int, right: Int): Int {
        if (left >= right) return nums[left]
        val mid = (left + right) / 2
        val lmax = helper(nums, left, mid - 1)
        val rmax = helper(nums, mid + 1, right)
        var mmax = nums[mid]
        var t = mmax
        for (i in mid - 1 downTo left) {
            t += nums[i]
            mmax = Math.max(mmax, t)
        }
        t = mmax
        for (i in mid + 1..right) {
            t += nums[i]
            mmax = Math.max(mmax, t)
        }
        return Math.max(mmax, Math.max(lmax, rmax))
    }
}