首页 > 试题广场 >

连续子数组最大和(ACM版本)

[编程题]连续子数组最大和(ACM版本)
  • 热度指数：31477 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
给定一个长度为 的数组，数组中的数为整数。
请你选择一个非空连续子数组，使该子数组所有数之和尽可能大。求这个最大值。

输入描述:
第一行为一个正整数 ，代表数组的长度。 1\leq n \leq 2 \cdot10^5
第二行为 个整数 a_i，用空格隔开，代表数组中的每一个数。


输出描述:
连续子数组的最大之和。
示例1

输入

3
3 -4 5

输出

5

说明

选择 [5] 这个子数组即可。
示例2

输入

3
4 -3 5

输出

6

说明

选择 [4,-3,5] 这个子数组。
算法知识视频讲解
添加回答
诗悦网络内推_有问必答头像 诗悦网络内推_有问必答

Erlang人生动态规划
解题思路

如果到目前为止你的过去是负担，那就放下吧，每天都是新的开始~

如果到目前为止你的过去是正担，那就带上吧，试试找到自己人生的最大子序和吧~（即自己相对提升最大的一段时间，我希望是现在也是未来）

代码

-spec max_sub_array(Nums :: [integer()]) -> integer().
max_sub_array(Nums = [NumH | NumsT]) ->
    do_max_sub_array(NumsT, #{nums => [NumH]}).

do_max_sub_array([Num | T], Args = #{nums := Nums = [PreSum | _]}) ->
    Sum = case PreSum >= 0 of
        true ->
            Num + PreSum;
        _ ->
            Num
    end,
    do_max_sub_array(T, Args#{nums := [Sum | Nums]});
do_max_sub_array([], _Args = #{nums := Nums}) ->
    lists:max(Nums).
发表于 2021-11-03 13:19:31 回复(2)
JavaScript Node
诺曼底法国头像 诺曼底法国
这个破B题是不是有问题，测试用例 1 1的那条自测没问题，但是提交就是显示过不去，输出为NaN
发表于 2023-09-21 16:34:58 回复(1)
C++
紧张的花生米在写日记头像 紧张的花生米在写日记
本题的 dp 数组代表的是下标为 i 时，子字符串以 i 结尾的最大和；
初始状态也就是 dp[0] 设为原数组的第一位；
dp[i] 为其前一个状态dp[i - 1]与原数组第 i 项的和跟原数组第 i 项中更小的值；
状态方程为：dp[i] = max(dp[i - 1] + v[i], v[i])
最后取dp的最大值即可； 
#include <iostream>
#include <vector>
using namespace std;
int main() {
    int n;
    cin >> n;
    vector<int> v;
    for (int i = 0; i < n; ++i) {
        int a;
        cin >> a;
        v.push_back(a);
    }
    vector<int> dp(n);
    dp[0] = v[0];
    for (int i = 1; i < n; ++i) {
        dp[i] = max(dp[i - 1] + v[i], v[i]);
    }
    int res = dp[0];
    for (int i = 0; i < n; ++i) {
        res = max(dp[i], res);
    }
    cout << res;
    return 0;
}


发表于 2022-04-24 20:44:35 回复(0)
C++
coder在开会头像 coder在开会
#include <iostream>
#include<vector>
#include<climits>
using namespace std;

int main() {
    int n;
    cin >> n;
    int nums[n];
    for(int i=0;i<n;i++){
        cin >> nums[i];
    }
    int current = nums[0];
    int global = nums[0];
    for(int i=1; i<n;i++){
        current = max(nums[i],current+nums[i]);
        global = max(current,global);
    }
    cout << global << endl;
}//简单易懂
发表于 2025-03-26 16:02:04 回复(0)
defaulter头像 defaulter 
#include <iostream>
using namespace std;

int main()
{
    int a[200005], n, dp[200005];
    cin >> n;
    for (int i = 0; i < n; i++)
        cin >> a[i];
    dp[0] = a[0];
    int res = dp[0];//这里注意赋值初始化不能为0，如果只有一个元素，可能导致进不去循环，最后输出res没有值哦
    for (int i = 1; i < n; i++)
    {
        dp[i] = max(dp[i - 1] + a[i], a[i]); // 如果遇到a[i]<0
        res = max(res, dp[i]);
    }
    cout << res;
}

发表于 2025-02-26 17:12:03 回复(0)
C++
Spectre_头像 Spectre_ 
#include <iostream>
using namespace std;

int main() {
    int n;
    cin >> n;
    int arr[n], dp[n];
    for (int i = 0; i < n; ++i) cin >> arr[i];
    // 时间复杂度O(N)，空间复杂度O(1)
    int dp0 = arr[0], dp1, res = arr[0];
    for (int i = 1; i < n; ++i) {
        // i位置处最大子数组和，一定包含i-1位置的数，这样才能保证连续
        dp1 = max(dp0 + arr[i], arr[i]);
        res = res > dp1 ? res : dp1;
        dp0 = dp1;
    }
    cout << res;
    return 0;
}

发表于 2022-10-31 14:25:22 回复(0)
牛客嗷嗷头像 牛客嗷嗷
时间复杂度：O(n)，空间复杂度：O(1) 
import java.util.Scanner;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        int n = in.nextInt();
        int [] nums = new int[n];

        for (int i = 0; i < n; i++)
            nums[i] = in.nextInt();

        int res = maxSubArray(nums);

        System.out.println(res);
    }

    static int maxSubArray(int[] nums) {
        int res = nums[0];
        for (int i = 1; i < nums.length; i++) {
            nums[i] += Math.max(nums[i - 1], 0);
            res = Math.max(res, nums[i]);
        }
        return res;
    }
}

发表于 2022-10-03 19:35:04 回复(0)
Python3
亦人头像 亦人
n = int(input().strip())
nums = input().strip().split(' ')
nums = list(map(int, nums))
for i in range(1, n):
    nums[i] = max(nums[i-1]+nums[i], nums[i])
print(max(nums))
发表于 2022-03-12 23:21:24 回复(0)
Python3
炼0805头像 炼0805 
n = int(input())
a=list(map(int,input().split()))
dp=[0 for _ in range(n)]
for i in range(n):
    dp[i]=max(a[i],dp[i-1]+a[i])
print(max(dp))


发表于 2025-05-08 11:08:38 回复(0)
C
cs小白_头像 cs小白_ 
#include <stdio.h>

int main() {
    int n,max;
    scanf("%d",&n);
    int a[n],dp[n];
    for (int i=0; i<n; i++) {
        scanf("%d",&a[i]);
    }
    dp[0]=a[0];
    max=dp[0];
    for (int i=1; i<n; i++) {
        dp[i]=(a[i]>(dp[i-1]+a[i])?a[i]:(dp[i-1]+a[i]));
        max=(dp[i]>max?dp[i]:max);
    }
    
        printf("%d", max);
    
    return 0;
}

发表于 2024-11-29 20:08:37 回复(0)
Go
牛客266312060号头像 牛客266312060号
真的无语，同样的代码，自测和提交输出的结果不同

发表于 2024-09-26 18:02:40 回复(0)
Javascript
刷多了都是泪头像 刷多了都是泪
如果遇到奇怪的结果，比如自测运行通过，但是保存并提交失败，大概是输入没有trim掉空格。
发表于 2024-09-23 17:07:52 回复(0)
牛客212561046号头像 牛客212561046号 
#include <iostream>
using namespace std;

int main() {
    int n, res = 0, sum=0;
    cin>>n;
    int x;
    cin>>x; 
    res = x; sum = x;
    while(--n){
        cin>>x;
        if(sum>0){
            res = max(res, sum);
            sum += x;
        }else{
            sum = x;
            res = max(res,sum);
        }
    }
    res = max(res,sum);
    cout<<res;
}
// 64 位输出请用 printf("%lld")

发表于 2023-12-27 16:22:21 回复(0)
C
大数据23102陈宏禹头像 大数据23102陈宏禹
#include<stdio.h>
int main()
{   int j,n,i,a[1000010],q[1000010];
    scanf("%d",&n);
    for(i=0;i<n;i++)
    scanf("%d",&a[i]);
    j=a[0];q[0]=a[0];
    for(i=1;i<n;i++)
    {   if(q[i-1]+a[i]>a[i])
        {
            q[i]=q[i-1]+a[i];
        }
        else
        {
            q[i]=a[i];
        }
        if(j<q[i])
        {
            j=q[i];
        }
       
    }
   
    printf("%d",j);
   
   
   
    return 0;
   
}
发表于 2023-12-06 23:42:02 回复(0)
Python3
LeoAlan头像 LeoAlan 
# 解法一
_ = input()
arr = list(map(int, input().split()))

# 初始化s为从第一个元素前开始连续相加的值
s = 0
# 初始化res为第一个元素的值
res = arr[0]

# 遍历数组
for i in arr:
    # 更新s
    s += i
    # 如果更新后的s比res大，则赋值给res
    res = max(s, res)
    # 如果更新后的s小于0，则清空值，从下一个元素开始更新
    s = max(s, 0)

# 最后res即为连续子数组的最大值
print(res)


# 解法二
n = int(input())
arr = list(map(int, input().split()))

dp = [arr[0]]
# 遍历数组
for i in range(1, n):
    # 连加后的值与下一个值作比较，如果连加后比较大，则不取下一个值；如果下一个值比较大，则从下一个值算起
    dp.append(max(arr[i], dp[i - 1] + arr[i]))

print(max(dp))

发表于 2023-10-13 10:02:44 回复(0)
Java
求你们别卷了2头像 求你们别卷了2
本题思路：
1.第一步，先获取到数组集合
2.第二步，如果数组只有一位数直接返回即可
3.第三步，我们定义dp数组的含义是存放子数组和最大值
4.第四步，确定最大值如何计算出来，因为是求子数组最大和，那么很容易想到有两种情况，添加当前值之前的数组和添加后相比哪一个更大，我们取最大的即可Math.max(sum,dp[i-1])
5.第五步，我们sum如何计算呢，又分两种情况，如果我们加了当前数比没加之前要小肯定就得放弃之前的方案，需要重新计算
6.第六步，返回dp[n-1]即可，因为我们定义的dp数组就是存放当前子最大和 
        public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int num = sc.nextInt();
        int[] a = new int[num];
        for (int i = 0; i < num; i++) {
            a[i] = sc.nextInt();
        }
        int sum = 0;
        int max = getMaxPlus(sum, a);
        System.out.println(max);
    }

    private static int getMaxPlus(int sum, int[] a) {
        if (a.length == 1) return a[0];
        int[] dp = new int[a.length];
        dp[0] = a[0];
        if (dp[0] > 0) sum += dp[0];
        for (int i = 1; i < a.length; i++) {
            sum += a[i];
            sum = Math.max(sum, a[i]);
            dp[i] = Math.max(sum, dp[i - 1]);
        }
        System.out.println(Arrays.toString(dp));
        return dp[a.length - 1];
    }


发表于 2023-08-11 17:17:20 回复(0)
Python 3
化骨重生头像 化骨重生
import sys

n=int(input())
L=list(map(int,input().split()))
k=-1
for i in range(n):
    if L[i]>0:
        k=i
        break
if k==-1:
    print(max(L))
elif k==n-1:
    print(L[-1])
else:
    sum1=0
    last=L[k]
    for i in range(k,n):
        if sum1<0 and L[i]>0:
            sum1=0
        sum1+=L[i]

        if sum1>last:
            last=sum1

    print(last)
发表于 2023-04-18 14:12:34 回复(0)
Python3
Namely头像 Namely 
import sys

nums = []
for line in sys.stdin:
    a = line.split()
    nums = a

m = len(nums)
# 定义dp[i]为选中第i元素的子数据最大值
# 输出为max(dp[1],...,dp[m])
# dp方程：dp[i+1] = max(dp[i] + nums[i], nums[i])
dp = [0] * (m+1)
max_res = -9999
for i in range(m):
    dp[i+1] = max(dp[i] + int(nums[i]), int(nums[i]))
    max_res = max(max_res, dp[i+1])
print(max_res)

发表于 2023-03-16 16:22:25 回复(0)
炸掉地球头像 炸掉地球 
#include <iostream>
using namespace std;
const int N = 200010;
int a[N];
int main()
{
    int n;
    cin >> n;
    for(int i = 0; i < n; i++)
        cin >> a[i];
    int ret = -101, sum = -101;
    for(int i = 0; i < n; i++)
    {
        sum = max(sum + a[i], a[i]);
        ret = max(ret, sum);
    }
    cout << ret << endl;
}
发表于 2022-11-28 20:21:20 回复(0)
Javascript
小谷围做题家头像 小谷围做题家 
const rl = require("readline").createInterface({ input: process.stdin });
var iter = rl[Symbol.asyncIterator]();
const readline = async () => (await iter.next()).value;

void async function () {
    let n=await readline();
    let arr=(await readline()).split(" ").map(it=>parseInt(it));
    let max=arr[0],sum=0;
    for(let i=0;i<arr.length;i++){
        sum+=arr[i];
        if(arr[i]>sum) sum=arr[i];
        if(sum>max) max=sum;
    }
    console.log(max);
}()

发表于 2022-11-20 21:45:56 回复(0)
提交观点

问题信息

难度：
46条回答 2388浏览

热门推荐

通过挑战的用户

查看代码

相关试题

连续子数组最大和(ACM版本)

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号