面试题42. 连续子数组的最大和

连续子数组的最大和

题目描述

输入一个整型数组，数组里有正数也有负数。数组中的一个或连续多个整数组成一个子数组。求所有子数组的和的最大值。

要求时间复杂度为O(n)

示例：

输入: nums = [-2,1,-3,4,-1,2,1,-5,4]
输出: 6
解释: 连续子数组 [4,-1,2,1] 的和最大，为 6。

提示：
1 <= arr.length <= 10^5
-100 <= arr[i] <= 100

转载来源：力扣（LeetCode）

题目分析

• 首先，我们要达成一个共识，对于A[i]，如果A[0] ~ A[i-1]的最大和小于0，那么A[i] ~ A[n]的最大和肯定与A[0] ~ A[i-1]的最大和无关，因为A[0] ~ A[i-1]的最大和是负的，只会帮倒忙
• 如果A[0] ~ A[i-1]的最大和大于0，那么A[0] ~ A[i] 的最大和就是 A[0] ~ A[i-1]最大和+A[i]，即使A[i] < 0（A[i]可以连通A[i-1]和A[i+1]）
• 每次更新A[i]的最大和，都和当前最大和比较一下，实时更新

    fun maxSubArray(nums: IntArray): Int {
        if(nums.isEmpty()) return 0;
        var maxSum = nums[0]
        var nowSum = nums[0]
        for(i in 1 until nums.size){
            if(nowSum < 0){
                nowSum = nums[i]
            }else{
                nowSum += nums[i]
            }
            if(nowSum > maxSum){
                maxSum = nowSum
            }
        }
        return maxSum
    }