子数组的最大累加和问题

[编程题]子数组的最大累加和问题

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

给定一个数组arr，返回子数组的最大累加和

例如，arr = [1, -2, 3, 5, -2, 6, -1]，所有子数组中，[3, 5, -2, 6]可以累加出最大的和12，所以返回12.

[要求]

时间复杂度为

，空间复杂度为

输入描述:

第一行一个整数N。表示数组长度
接下来一行N个整数表示数组内的元素

输出描述:

输出一个整数表示答案

示例1

输入

7
1 -2 3 5 -2 6 -1

输出

备注:

算法知识视频讲解

查看答案及解析

helloxuanbao

#include <stdio.h>
#include <stdlib.h>
#include <limits.h>

#define max(a,b) ((a) > (b) ? (a) : (b))

int main(void) {
    int n, *arr;
    scanf("%d", &n);
    arr = (int *) malloc(n * sizeof(int));
    for (int i = 0; i < n; i++) {
        scanf("%d", arr + i);
    }
    
    int maxSum = INT_MIN, pre = -1, cur;
    for (int i = 0; i < n; i++) {
        cur = arr[i] + (pre > 0 ? pre : 0);
        maxSum = max(maxSum, cur);
        pre = cur;
    }
    printf("%d\n", maxSum);
    return 0;
}

发表于 2022-04-04 21:10:09 回复(0)