面试题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
    }

©著作权归作者所有,转载或内容合作请联系作者
【社区内容提示】社区部分内容疑似由AI辅助生成,浏览时请结合常识与多方信息审慎甄别。
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

相关阅读更多精彩内容

友情链接更多精彩内容