[数据结构与算法]01-复杂度2 Maximum Subsequence Sum (25 分)注意事项

01-复杂度2 Maximum Subsequence Sum (25 分)

题目

题目截图如下：

一、代码

c++代码如下：

#include <iostream>
using namespace std;

int main()
{
    int K;
    cin >> K;

    int *a = new int[K];
    int thisSum = 0;
    int MaxSum = -1;
    int First, End, temp_First;

    for (int i = 0; i < K; i++)
        cin >> a[i];
    First = a[0];
    temp_First = a[0];


    for (int i = 0; i < K; i++)
    {
        thisSum += a[i];

        if (thisSum > MaxSum)
        {
            End = a[i];
            MaxSum = thisSum;
            First = temp_First;
        }
        else if (thisSum < 0)
        {
            thisSum = 0;
            temp_First = a[i + 1];
        }
    }
    if (MaxSum < 0)
        cout << 0 << " " << a[0] << " " << a[K - 1] << endl;
    else
        cout << MaxSum << " " << First << " " << End << endl;
    return 0;
}

运行结果

二、关键代码

1.对一维数组的动态存储空间分配

代码如下

int *a = new int [K];

具体用法可以参考：《数据结构、算法与应用 C++语言描述》

2. “在线处理” 算法

代码：

 int thisSum = 0;
    int MaxSum = -1;
    int First, End, temp_First;

    for (int i = 0; i < K; i++)
        cin >> a[i];
    First = a[0];
    temp_First = a[0];


    for (int i = 0; i < K; i++)
    {
        thisSum += a[i];

        if (thisSum > MaxSum)
        {
            End = a[i];
            MaxSum = thisSum;
            First = temp_First;
        }
        else if (thisSum < 0)
        {
            thisSum = 0;
            temp_First = a[i + 1];
        }
    }

注意细节：
1：

First = a[0];
tempt_First = a[0];

保证了当First与temp_First能够最开始存储第一个元素，而不是将First 与 temp_First均在最开始被初始化为0！！！！否则的话，若只有一个整数，会出错！！！

2：
temp_First 的用法！！

三：总结

此题主要利用：在线处理、动态分配存储空间等，还有就是注意细节