【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的数),然后去比较大小,然后对结果进行重新比较赋值即可。