算法题每日一练：连续子数组的最大和

作者：知心宝贝

2023-04-27
江苏
本文字数：842 字
阅读完需：约 3 分钟

一、问题描述

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

题目链接：连续子数组的最大和

二、题目要求

要求：

1 <= arr.length <= 10^5
-100 <= arr[i] <= 100
要求时间复杂度为 O(n)。

示例:

输入: nums = [-2,1,-3,4,-1,2,1,-5,4]输出: 6解释: 连续子数组 [4,-1,2,1] 的和最大，为 6。

复制代码

考察

1.动态规划中等题型2.建议用时5~15min

复制代码

三、问题分析

这也是一道比较典型的动态规划问题，动态规划没做过的可以看这一篇入门题解：

算法题每日一练---第34天：青蛙跳台阶

还是用我们的三步走老套路：

第一步含义搞懂：

这一题在力扣上面是简单题，但我第一次做想了半天要怎么往动态规划上面靠拢，瞬间觉得这一题不简单。

先看题目要求是什么，求出数组中连续子数组的最大值，下面就以示例里面的值讲解。

设一维数组 dp[i]就代表从区间 1~i 的范围里面，以 num[i]结尾的连续子数组最大值。

第二步变量初始：

这一题我们只需要初始一个变量就行，那就是 dp[0]=nums[0]

第三步规律归纳：

这一步就是最关键的一步了，能不能娶上媳妇就看最后一哆嗦了。

我先把 nums 数组和 dp 数组里面的值列举一下，看看能不能发现规律：

仔细看一下，每一个 dp[i]是如何得到的，是不是当前位的 num[i]加上前面一个 dp[i-1]数又或是没加，那没加是因为前面的数是负的嘛。所以，规律出现：

三步走，打完收工！

四、编码实现

#include<iostream>using namespace std;int main(){    long long int i,n,dp[100005],nums[100005],max;//初始化变量    cin>>n;//输入数组大小    for(i=0;i<n;i++)    {      cin>>nums[i];//输入数组数据  }    max=dp[0]=nums[0];//变量初始    for(i=1;i<n;i++)//循环判断    {        if(dp[i-1]<=0)//负数是本身        {            dp[i]=nums[i];        }        else            dp[i]=nums[i]+dp[i-1];//正数加上上一个        if(dp[i]>max)//是否大于当前max        {            max=dp[i];        }    }    cout<<max;//输出结果  return 0;}