連續(xù)子數(shù)組的最大和

題目描述

輸入一個整型數(shù)組，數(shù)組里有正數(shù)也有負(fù)數(shù)。數(shù)組中的一個或連續(xù)多個整數(shù)組成一個子數(shù)組。求所有子數(shù)組的和的最大值。

要求時間復(fù)雜度為O(n)

示例：

輸入: nums = [-2,1,-3,4,-1,2,1,-5,4]
輸出: 6
解釋: 連續(xù)子數(shù)組 [4,-1,2,1] 的和最大，為 6。

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

轉(zhuǎn)載來源：力扣（LeetCode）

題目分析

• 首先，我們要達(dá)成一個共識，對于A[i]，如果A[0] ~ A[i-1]的最大和小于0，那么A[i] ~ A[n]的最大和肯定與A[0] ~ A[i-1]的最大和無關(guān)，因?yàn)锳[0] ~ A[i-1]的最大和是負(fù)的，只會幫倒忙
• 如果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]的最大和，都和當(dāng)前最大和比較一下，實(shí)時更新

    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
    }