我要招人

去企业版

首页 > 试题广场 >

连续子数组最大和

[编程题]连续子数组最大和

热度指数：27250 时间限制：C/C++ 2秒，其他语言4秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

给定一个长度为 $n\$ 的数组，数组中的数为整数。

请你选择一个非空连续子数组，使该子数组所有数之和尽可能大，子数组最小长度为1。求这个最大值。

输入描述:

第一行为一个正整数 ，代表数组的长度。 
第二行为 个整数 ，用空格隔开，代表数组中的每一个数。

输出描述:

连续子数组的最大之和。

示例1

输入

8
1 -2 3 10 -4 7 2 -5

输出

说明

经分析可知，输入数组的子数组[3,10,-4,7,2]可以求得最大和为18

示例2

输入

1
2

输出

示例3

输入

1
-10

输出

-10

算法知识视频讲解

其实是牛哥

发表于 2021-10-19 15:09:37

精华题解子数组最大连续和难度：2星解法1 动态规划定义 dp[i]dp[i]dp[i] 为前 iii 个数中，以第 iii 个数结尾的子数组最大连续和。于是有转移方程： dp[i]=max(dp[i−1]+a[i],a[i])dp[i]=max(dp[i-1]+a[i],a[i])dp[i]=max 展开全文

诗悦网络内推_有问必答

发表于 2021-11-02 00:16:51

解题思路如果到目前为止你的过去是负担，那就放下吧，每天都是新的开始~ 如果到目前为止你的过去是正担，那就带上吧，试试找到自己人生的最大子序和吧~（即自己相对提升最大的一段时间，我希望是现在也是未来）代码 -spec max_sub_array(Nums :: [integer()]) -> 展开全文

蘑菇睡不着

发表于 2021-10-16 15:42:03

描述给定一个长度为的数组，数组中的数为整数。请你选择一个非空连续子数组，使该子数组所有数之和尽可能大。求这个最大值。示例1 输入： 3 3 -4 5 输出： 5 说明：选择 [5] 这个子数组即可。示例2 输入： 3 4 -3 5 输出： 6 说明：选择 [4,-3,5] 这展开全文

程序猿大队长

发表于 2021-12-02 09:01:07

解题步骤 1.确定状态数组下标不断移动，在移动过程中，最大子数组也不断变化，所以状态为子数组最大值。 2.确定dp数组在本题中，可定义一维数组dp[x]，其中dp[i]表示以第i个元素结尾最大子数组的值 3.确定选择针对第i个元素，实际上是有两种选择，一种是与arr[i-1]相连，形成一个最大展开全文

牛客484960258号

发表于 2021-12-30 10:12:04

while True: try: a = int(input()) b = list(map(int,input().split())) dp = [0]*a for i in range(a): if 展开全文

破竹GYH

发表于 2022-02-02 20:42:57

#include<iostream> using namespace std; int main() { int n; cin>>n; int a[900000]; for(int i=0;i<n;i++) { 展开全文

永往直前

发表于 2022-04-17 00:04:13

// 注意类名必须为 Main, 不要有任何 package xxx 信息 public class Main { public static void main(String[] args) { Scanner in = new Scanner(System.in); 展开全文

fred-coder

发表于 2021-10-31 14:40:50

根据题意，求解连续数组的最大值，利用动态规划的思想，则可创建动态数组，然后赋值初始值，再根据状态转移方程进行遍历；本题中求解的是连续数组的最大值，设 dp[i] 表示数组 data[:i] 的最大值, 其值与 dp[i - 1] 和当前值 data[i] 有关, 若 dp[i - 1] + dat 展开全文

小菲柱

发表于 2022-04-19 20:00:04

#include <algorithm> #include <iostream> #include <vector> int main(int argc, char *argv[]) { int size; std::cin >> si 展开全文

牛客864125390号

发表于 2023-03-30 21:17:54

import sys """ 用前缀和做，时间复杂度为o(n^2),在本题中会超时下面是动态规划解决，时间复杂度为o(n),解决超时问题 n = int(input()) l = list(map(int, input().split())) for i in range(1, len(l)): 展开全文