以下為題目描述：
01-復雜度2 Maximum Subsequence Sum （25 分）
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.
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.
Sample Input:
10
-10 1 2 3 4 -5 -23 3 7 -21
Sample Output:
10 1 4
在線演算法：
以下為源代碼：
#include<iostream>
#define MAX 100000
using namespace std;
int func(int a[],int n,int &start,int &end)
{
int j = 0,count = 0;
int flag = 1;
int TheSum = 0,MaxSum = -1;
for(int i = 0;i<n;i++)
{
TheSum += a[i];
if(a[i]<0)count++;
if(TheSum>MaxSum)
{
if(flag)
{
start = i;
flag = 0;
}
end = i;
MaxSum = TheSum;
}
else if(TheSum<0)
{
TheSum = 0;
flag = 1;
}
}
if(count==n)return -1;
return MaxSum;
}
int main()
{
int n = 0,max = 0;
int start = 0,end = 0;
int a[MAX] = {0};
cin>>n;
for(int i = 0;i < n;i++)
{
cin>>a[i];
}
max = func(a,n,start,end);
if(max<0)
cout<<"0"<<" "<<a[0]<<" "<<a[n-1]<<endl;
else
cout<<max<<" "<<a[start]<<" "<<a[end]<<endl;
return 0;
}
過不去的測驗點描述：并列和對應相同i但是不同j，即尾是0 答案錯誤
這個不是如果由兩個相同大小的最大子序列，取下標最小的那個嗎，我用的start和end記錄處理的，測驗了幾個數都沒錯，取得是最小的下標值，但是測驗點就是不過，求大佬指點！！
uj5u.com熱心網友回復：
91 5 0 -9 2 4 0 -9 0
6 1 5
可能是這種序列不通過？
uj5u.com熱心網友回復：
通過了也報錯，哭了uj5u.com熱心網友回復：
供參考：#include<iostream>
#define MAX 100000
using namespace std;
int func(int a[],int n,int &start,int &end)
{
int flag = 0;
int TheSum = 0,MaxSum = -1;
for(int i = 0;i<n;i++)
{
TheSum += a[i];
if(TheSum>MaxSum)
{
start = flag;
end = i; //最大子段和最右端的下標
MaxSum = TheSum;
}
else if(TheSum<0)
{
TheSum = 0;
flag = i+1;//最大子段和最左端的下標
}
}
return MaxSum;
}
int main()
{
int n = 0,max = 0;
int start = 0,end = 0;
int a[MAX] = {0};
cin>>n;
for(int i = 0;i < n;i++)
{
cin>>a[i];
}
max = func(a,n,start,end);
if(max<0)
cout<<"0"<<" "<<a[0]<<" "<<a[n-1]<<endl;
else
cout<<max<<" "<<a[start]<<" "<<a[end]<<endl;
return 0;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/266791.html
標籤：C++ 語言
下一篇：【C語言求助】