连续子数组最大和

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

热度指数：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

算法知识视频讲解

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)