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

[编程题]连续子数组最大和(ACM版本)

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

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

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

输入描述:

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

输出描述:

连续子数组的最大之和。

示例1

输入

3
3 -4 5

输出

说明

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

示例2

输入

3
4 -3 5

输出

说明

选择 [4,-3,5] 这个子数组。

算法知识视频讲解

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)