【LeetCode打卡】剑指 offer 42.连续数组的最大子数和

前言

-🏀大家好,我是BXuan,热爱编程与篮球的软件工程大二学生一名 -📚当爱上Coding&&Studying的那一刻… -🏃放弃不难,但坚持一定很酷。

🏆剑指 offer 42.连续数组的最大子数和

🔊问题描述:

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

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

🏀输入输出示例:

示例1: 输入: 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

🥇代码示例:

class Solution {
          
   
    public int maxSubArray(int[] nums) {
          
   
        //动态规划
        //为什么刚开始要定义res=nums[0]呢?
        //因为如果只有一个元素的话,需要返回的就是该值,而不是0或者其他的。
        int res = nums[0];
        int sum = 0;
        //对数组进行遍历
        for(int num : nums){
          
   
        	//这一步其实就是在判断,当后面的数使得整体和减小的时候,果断舍弃。
        	//寻找下一个使和增大的数,即实现了滑动窗口。
            sum = Math.max(sum+num, num);
            res = Math.max(sum, res);
        }
        return res;
    }
}

🔑解题思路

本题就是一个简单的动态规划的问题,那么如何得到最优解呢? 首先就是对题目的理解,题目的意思就是得到连续的最大的子数组和,那么首先需要对每个数字进行判断,加上这个数字之后能变大或者减小(减小的情况肯定是该数是小于0的数),然后去比较大小,然后对结果进行重新比较赋值即可。

经验分享 程序员 微信小程序 职场和发展