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.
Copy the code

Example 2:

Input: nums = [1]
Output: 1
Copy the code

Example 3:

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

 

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.

Solution a:

The sum of the maximum subarray is O(n), and the Divide and Conquer Approach is also used. Define two variables, result and curSum, where res holds the final result to be returned, i.e., the sum of the largest subarray, curSum starts at 0, num is iterated each time, and the larger values in curSum + num and num are stored in curSum. Then the larger values in result and curSum are stored in result, and so on until the entire array is iterated, and the largest subarray values are stored in result, as follows:

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
    }
}
Copy the code

Method 2:

We need to Divide an array into two parts, find the largest sum on the left and the largest on the right, and then start from the middle and scan left and right. The maximum value obtained is compared with the maximum value obtained on the left and right sides to obtain the largest one. The code is as follows:

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))
    }
}
Copy the code