PAT-数据结构-例题

忘是亡心i 2021-09-28 06:18 249阅读 0赞

# **01-复杂度2 Maximum Subsequence Sum （25 分）** #

> Given a sequence of K integers \{ N1, N2, …, NK \}. A  
> continuous subsequence is defined to be \{ Ni, Ni+1, …, Nj \}  
> 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.

# **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.

# **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.

这道题是最大子列和的强化版本，为什么称它是强化版本呢，因为它相比原来的题多输出了最大子列和的首项和尾项。  
分析题目要求  
1.最大子列和  
2.首项，尾项  
其中第一个要求可以通过在线处理解决。  
第一个要求的样例代码如下

for (i = 0; i < k; i++)
    { 
    	cin >> arry[i];//输入数组
    }
    for (i = 0; i < k; i++)
    { 
    		a += arry[i];
    		if (a > b)//如果关于arry的子列和大于所存的B，更新一次B
    		    b = a;
    		if (a < = 0)//如果加入arry[i]使得数组成为负数，舍去，并将a变为0
    			a = 0;
    		}
    cout << b << endl;

第二个要求是输出首项和尾项  
博主选择的是进行标记，因为每更新一次b的情况下都要更新尾项，因此，我第一个更新B大小的判断中加入了对尾项的标记字母d，且d与i的大小是同步的  
即为

if (a > b)
    { 
         d = i;
         b = a;
    }

那么如何对首进行标记呢？我用了一个笨办法，即为数个数，何为数个数，第一次更新b的数是首项目，但不一定是答案要求的首项，为什么这么说呢，因为存在后面的子列和大于前面所形成的子列和，因此我引入了z进行计数。然后用c保存我所记的z的数值，即为

if (a > b)
    { 
        d = i;
        c = z;
        b = a;
        z++;
    }

表面上看起来是对的，但是测试的样例中有这样一例子，如果最大子列和中存在负数该怎么办？  
显然我这样的代码对首项的判定是有一定的误差的，因此我添加了

else if (a > = 0)
    z++;

条件为什么是大于等于0而不是大于0呢，因为大于0时，若a=0，那么最后一项使得原式等于0，但后面的项数又使得其达到B甚至超过B，那么这种情况题要求全部概括的，如果不用大于等于0的话，那么出来的首项会出现问题

针对arry\[i\]使得a变为负数时，对a清零的同时对z清零

if (a < 0)
    { 
        a = 0;
        z = 0;
    }

是不是上述的东西合起来就成为所需要的代码了呢，还不够，因为样例中还有两种特殊情况，全为0的时候和全为负数的情况。  
针对这两种情况，我分别做了以下限制；

if(s==k)//在对数据处理的时候加上对arry数组正负的判断，如果arry[i]小于0，那么s++；统计arry数组中负数的个数s是否等于输入的总个数k
    { 
       cout<<"0 ";
       cout<<arry[0];
       cout<<" ";
       cout<<arry[k-1]<<endl;
       continue;
    }
    if(d==-1)//这里我对标记尾项的d进行了初始化的特殊处理，让d=-1，如果上述对数据有过对b的修改的话，那么d一定会被修改，且-1是不可能出现的数组下标；
    { 
       cout<<"0 0 0"<<endl;
       continue;
    }

要点就这么多，整体的样例代码为

#include<bits/stdc++.h>
    using namespace std;
    int i;
    int a,b,c,d;
    int z;
    int main()
    { 
        int k,s;
        int arry[100005];
        while(cin>>k)
        { 
            s = 0;
            a = 0;
            b = 0;
            z = 0;
            d = -1;
            memset(arry, 0, sizeof(arry));
            for (i = 0; i < k; i++)
            { 
                cin >> arry[i];
            }
            for (i = 0; i < k; i++)
            { 
                a += arry[i];
                if (a > b)
                { 
                    d = i;
                    c = z;
                    b = a;
                    z++;
                }
                else if(a>=0)
                    z++;
                if (a < 0)
                { 
                    a = 0;
                    z=0;
                }
                if(arry[i]<0)
                    s++;
            }
            if(s==k)
            { 
                cout<<"0 ";
                cout<<arry[0];
                cout<<" ";
                cout<<arry[k-1]<<endl;
                continue;
            }
                    if(d==-1)
            { 
                cout<<"0 0 0"<<endl;
                continue;
            }
            cout<<b;
            cout<<" ";
            cout<<arry[d-c];
            cout<<" ";
            cout<<arry[d]<< endl;
        }
        return 0;
    }

数据结构和C++的初学者，代码有什么格式上的问题或者算法优化欢迎在评论区中进行指正  
2019年3月4日星期一01:03