我要招人

去企业版

首页 > 试题广场 >

最大子数组和

[编程题]最大子数组和

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

给定一个长度为 $n$ （ $1≤n≤10^5$ ）的整数数组 $a_1,a_2,a_3...,a_n$ $(-1000≤a_i≤1000)$ ,现在请你找出该数组的一个子数组，使得这个子数组的元素和最大

选择的子数组长度不能为0

输入描述:

第一行包含一个整数 $n$ ，表示数组的长度

第二行包含 $n$ 个整数 $a_1,a_2,...,a_n$ ，表示数组

输出描述:

输出为一个整数表示答案

示例1

输入

7
2 -4 3 -1 2 -4 3

输出

说明

显然，选择子数组，其总和最大，答案为4

算法知识视频讲解

小狐今天睡大觉

发表于 2025-12-28 00:01:24

使用动态规划解决。建立dp数组，初始化置零，dp[i]表示从首位到i的当前最大子数组的和。因为数据范围-10000~10000，所以会有一种情况：前面的数的和加上当前数字，结果反而没有当前数字大，说明前面的数字的和是负数，拖了真正的大数(当前数字)的后腿。这种情况下就要丢掉前面的数，从当前数字算起。展开全文

Ldh1315109

发表于 2025-11-11 17:58:01

fmin = lambda x, y: x if x < y else y fmax = lambda x, y: x if x > y else y def solve(testcase): n = II() A = LII() if all (a < 展开全文

周康禧

发表于 2025-12-10 22:37:44

#include <bits/stdc++.h> using namespace std; using ll = long long int; using ld = long double; using PII=pair<ll,ll>; using PIII=pair< 展开全文

WasserSingen

发表于 2026-04-17 02:28:22

//新手最易上手的方法#include <iostream>using namespace std;int main() { ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);//加速输入输出可省略 int 展开全文

nous1

发表于 2026-02-06 18:10:49

#include <bits/stdc++.h> #include <sys/types.h> #include <vector> using namespace std; int main() { int n; cin>>n; 展开全文

自由的风0450

发表于 2025-11-14 13:41:11

#include <iostream> #include<vector> using namespace std; int main() { int n; cin>>n; vector<int>a(n); for(in 展开全文

ccl_aurora

发表于 2026-02-07 11:39:54

#include <iostream> #include <vector> #include <algorithm> using namespace std; int main() { int n; cin >> n; int 展开全文

牛客用户098471297

发表于 2025-12-02 09:31:58

#include<bits/stdc++.h> using namespace std; #define int long long #define endl '\n' #define quick ios::sync_with_stdio(false);cin.tie(0);cout.t 展开全文

丘馗

发表于 2026-01-19 11:45:30

#include <iostream> #include <vector> using namespace std; int main() { int n;cin>>n; vector<int> nums(n); //输入数据展开全文

金刚侠

发表于 2025-12-20 11:03:40

#include <iostream> using namespace std; #include <vector> #include <algorithm> int main() { int n; cin>>n; vector<in 展开全文

问题信息

难度：

1条回答 10收藏 77浏览

最大子数组和

输入描述:

输出描述:

输入

输出

说明

问题信息

热门推荐

相关试题