Leetcode 53 最大子数组和

2023-12-20 11:31:23

题意理解

? ? ? ? 给定一个数列,求连续的子序列的和最大可以是多少?

????????子数组?是数组中的一个连续部分。

? ? ? ? 比如:

????????nums = [-2,1,-3,4,-1,2,1,-5,4]

? ? ? ? 最大子序列的和:6(4-1+2+1)

解题思路

? ? ? ? 使用贪心的思路来解题,则需要定义局部最优解和全局最优解,及分析之间的关系

? ? ? ? 当遍历到第i个元素时,当前子序列和为负数时,与其继续累加子序列的值不如设其之前的子序列

? ? ? ? 因为:负数之后拖累子序列和,

? ? ? ? 所以,我们需要再合适的地方舍弃子序列和为负的子序列——即合适的位置开启一个结果可能为正的子序列

? ? ? ? 又因为我们要求一个最大的子序列和

? ? ? ? 所以我们需要一个值来记录最大子序列和,其总揭露最大子序列和和当前子序列和的最大值。

? ? ? ? 最终,我们能得到连续子序列的最大值。

1.贪心解题

我们使用result来记录最大子序列和,curSum来记录当前子序列和。

注意

????????当且仅当数组只有一个元素时,则最大子序列和即为这个元素,即使这个元素可能时负数

? ? ? ? 如果一个序列的元素全为负数的话,其最大子序列和为该序列中最大的负数,因为其和任何一个负数相加都会变得更小

所以result和curSum从nums[0]初始化,遍历应从i=1处开始。

? ? ? ? 当只有一个元素时,返回当前值,

????????curSum为负,子序列和总是从0累加当前值。

public int maxSubArray(int[] nums) {
        int result=nums[0];
        int curSum=nums[0];
        for(int i=1;i<nums.length;i++){
            curSum=Math.max(curSum,0);//不从负数累加
            curSum+=nums[i];
            result=Math.max(curSum,result);
        }
        return result;
    }

2.分析

时间复杂度:O(n)

空间复杂度:O(n)

文章来源:https://blog.csdn.net/lt_BeiMo/article/details/135101700
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。