求最大连续子数组和

题目描述
给定一个数组a[0,...,n-1],求其最大子数组(长度>=1)和

输入描述
第一行一个整数n(1<=n<=5000)，然后依次输入n个整数（每个整数范围[-5000, 5000]）

输出描述
输出一个整数表示最大子数组和

样例输入
5
1 -1 1 1 -1

样例输出
2

首先使用最暴力的枚举法：

#include <iostream>
using namespace std;

int main() {
    int a, b=0, *p1, *p2;
    cin >> a;
    p1 = new int[a];

    //初始化p2数组，用来存放p1数组每一个子数组的和
    for (int i = 1; i <= a; i++){
        b += i;
    }
    b = b - 1;//去掉子数组包含原数组所有元素的情况
    p2 = new int[b];
    for (int i = 0; i < b; i++){
        p2[i] = 0;
    }

    //p2数组每个元素赋值
    for (int i = 0; i < a; i++){
        cin >> p1[i];
    }
    int num = 0;
    for (int i = 0; i < a; i++){
        for (int j = i; j < a; j++){
            for (int k = i; k <= j; k++){
                p2[num] += p1[k];
            }
            num++;
        }
    }

    //找出p2数组元素最大的值，放到p2[0]中
    for (int i = 1; i < b; i++){
        if (p2[0] < p2[i]){
            int temp = p2[0];
            p2[0] = p2[i];
            p2[i] = temp;
        }
    }

    //排除掉p2数组元素最大值为p1数组所有元素和的情况
    int c = 0;
    for (int i = 0; i < a; i++){
        c += p1[i];
    }
    if (p2[0] == c)
        p2[0] = -5000;

    //再执行一次，找出p2数组元素最大的值，放到p2[0]中
    for (int i = 1; i < b; i++){
        if (p2[0] < p2[i]){
            int temp = p2[0];
            p2[0] = p2[i];
            p2[i] = temp;
        }
    }

    cout << p2[0] << endl;

    return 0;
}

image.png

  结果得不到满分，因为时间超限。接下来要对算法进行改进。