PAT Advanced 1007. Maximum Subsequence Sum

1. Problem Description:

Given a sequence of \(K\) integers { \(N_1, N_2, ..., N_K\) }. A continuous subsequence is defined to be { \(N_i, N_{i+1}, ..., N_j\) } where \(1≤i≤j≤K\). The Maximum Subsequence is the continuous subsequence which has the largest sum of its elements. For example, given sequence { -2, 11, -4, 13, -5, -2 }, its maximum subsequence is { 11, -4, 13 } with the largest sum being 20.

Now you are supposed to find the largest sum, together with the first and the last numbers of the maximum subsequence.

2. Input Specification:

Each input file contains one test case. Each case occupies two lines. The first line contains a positive integer \(K\) (\(≤10000\)). The second line contains \(K\) numbers, separated by a space.

3. Output Specification:

For each test case, output in one line the largest sum, together with the first and the last numbers of the maximum subsequence. The numbers must be separated by one space, but there must be no extra space at the end of a line. In case that the maximum subsequence is not unique, output the one with the smallest indices \(i\) and \(j\) (as shown by the sample case). If all the \(K\) numbers are negative, then its maximum sum is defined to be 0, and you are supposed to output the first and the last numbers of the whole sequence.

4. Sample Input:

10
-10 1 2 3 4 -5 -23 3 7 -21

5. Sample Output:

10 1 4

6. Performance Limit:

Code Size Limit
16 KB
Time Limit
200 ms
Memory Limit
64 MB

思路：

一开始想着建立二维数组sum[MAX_COUNT][MAX_COUNT]存储每一种子序列的和，但是\(10^8\)的量级会超出内存限制，后面把sum改成vector<vector<int>>类型，让系统自行维护内存，此时sum最多占用\(4 \times 10^8 / 2 = 200 \times 10^6 = 200\)MB，仍然会超出内存限制，最后发现只需要维护好子序列和的最大值即可，不需要将所有的和存储下来，这种方法需要暴力搜索两次，但仍然能满足时间要求。。。第一次提交时testpoint4报wrong answer，testpoint7报超出内存限制，其中testpoint4是所有数字为负数时输出后忘了直接return，testpoint7参见上述思路，修改后AC。

参见大佬代码：1007. Maximum Subsequence Sum (25)-PAT甲级真题（最大连续子序列和、动态规划dp）_柳婼的博客-CSDN博客 ，比较简洁，动态规划的思路还是没搞太懂。。。

My Code & Result:

// #include <iostream>
// #include <ctime>
// #include <vector>

// // #define MAX_COUNT 10000

// using namespace std;

// // first submit testpoint 4 wrong answer, testpoint 7 Memory Limit Exceeded
// int main(void)
// {
//     //clock_t start=0, end=0;
//     int k=0;
//     // int sum[MAX_COUNT][MAX_COUNT] = {0}; // 10^8 magnitude will exceed memory limit
//     int i=0, j=0; // iterator
//     int maxSum=-1;
//     int temp=0;
//     int allNegative=1; // all negative flag
    
//     //start = clock();

//     cin >> k;
//     // vector<vector<int>> sum(k, vector<int>);
    
//     vector<vector<int> > sum(k, vector<int>());
//     for(i=0; i<k; ++i)
//     {
//         //cin >> sum[i][i];
//         cin >> temp;
//         sum[i].push_back(temp);

//         if(temp > maxSum) maxSum = temp;
//         if(temp >= 0) allNegative = 0; // have nonnegative number
//     }

//     if(allNegative)
//     {
//         cout << 0 << " " << sum[0][0] << " " << sum[k-1][0] << endl;
//         return 0; // this fixed testpoint 4
//     }
    

//     for(i=0; i<k; ++i)
//     {
//         for(j=i+1; j<k; ++j)
//         {
//             //sum[i].push_back(sum[i][j-1]+sum[j][0]); // this way is wrong
//             sum[i].push_back(sum[i].back()+sum[j][0]);

//             if(sum[i].back() > maxSum) maxSum = sum[i].back();
//         }
//     }

//     for(i=0; i<k; ++i)
//     {
//         for(j=0; j<sum[i].size(); ++j)
//         {
//             if(sum[i][j] == maxSum) // find maxSum
//             {
//                 cout << maxSum << " " << sum[i][0] << " " << sum[i+j][0] << endl;
//                 return 0;
//             }
//         }
//     }

    
//     // for(i=0; i<k; ++i)
//     // {
//     //     for(j=0; j<sum[i].size(); ++j)
//     //     {
//     //         cout << sum[i][j] << " ";
//     //     }
//     //     cout << endl;
//     // }
    

    
//     // for(i=0; i<MAX_COUNT; ++i)
//     // {
//     //     for(j=0; j<MAX_COUNT; ++j)
//     //     {
//     //         sum[i][j] = 1;
//     //         //cout << sum[i][j] << " "; // output will consume much time
//     //     }
//     //     //cout << endl;
//     // }
    
//     //end = clock();

//     // cout << end-start << endl;
//     // cout<<"time = "<<double(end-start)/CLOCKS_PER_SEC*1000<<"ms"<<endl;  //输出时间（单位：ms）

//     return 0;
// }



#include <iostream>
#include <vector>

using namespace std;

// first submit testpoint 4 wrong answer, testpoint 7 Memory Limit Exceeded
// this way fixed testpoint 7
int main(void)
{
    int k=0;
    int i=0, j=0; // iterator
    int maxSum=-1;
    int temp=0;
    int allNegative=1; // all negative flag

    cin >> k;
    
    // vector<vector<int>> sum(k, vector<int>);
    
    vector<vector<int> > sum(k, vector<int>());
    for(i=0; i<k; ++i)
    {
        //cin >> sum[i][i];
        cin >> temp;
        sum[i].push_back(temp);

        if(temp > maxSum) maxSum = temp;
        if(temp >= 0) allNegative = 0; // have nonnegative number
    }

    if(allNegative)
    {
        cout << 0 << " " << sum[0][0] << " " << sum[k-1][0] << endl;
        return 0; // this fixed testpoint 4
    }

    for(i=0; i<k; ++i)
    {
        temp = sum[i][0];
        for(j=i+1; j<k; ++j)
        {
            temp += sum[j][0];
            if(temp > maxSum) // find maxSum
            {
                maxSum = temp;
            }
        }
    }

    for(i=0; i<k; ++i)
    {
        temp = 0;
        for(j=i; j<k; ++j)
        {
            temp += sum[j][0];
            if(temp == maxSum)
            {
                cout << maxSum << " " << sum[i][0] << " " << sum[j][0] << endl;
                return 0;
            }
        }
    }
    
    return 0;
}

Compiler
C++ (g++)
Memory
988 / 65536 KB
Time
84 / 200 ms