Question

杭电oj1003题总是显示Wrong Answer，求指点，谢谢

#include<iostream>
#include<string>
using namespace std;

void main()//最大子序列和
{
int t, n, *a, max, *sum_max;
int k_start, k_end;
cin >> t;
for (int i = 0; i < t; i++)
{
cin >> n;
if (n >= 1 && n <= 100000)
{
a = (int*)malloc(n*sizeof(int));//动态数组
sum_max = (int*)malloc(n*sizeof(int));

for (int j = 0; j < n; j++)
{
cin >> a[j];
}

k_start = k_end = 1;
sum_max[0] = a[0];
max = sum_max[0];

for (int k = 1; k < n; k++)
{
if (sum_max[k - 1] >= 0)
{
sum_max[k] = a[k] + sum_max[k - 1];
if (sum_max[k]>max)
{
max = sum_max[k];
k_end = k + 1;
}
}
else
{
sum_max[k] = a[k];
if (sum_max[k] > max)
{
max = sum_max[k];
k_start = k + 1;
k_end = k + 1;
}
}
}

cout << "Case " << i + 1 << ":" << endl;
cout << max << " " << k_start << " " << k_end << endl;

if (i < t - 1)
{
cout << endl;
}
free(a);
}
}
}

Answer 1

//对于楼主的原代码,用如下数据进行测试:
//1
//10 -5 -6 3 2 1 -7 6 3 -10 8
//Case 1:
//9 3 8 (楼主原代码的输出,有误) 正确的应该是9 7 8
//楼主的原代码,能计算出最大值,能定出k_end,
//但是,不能定出正确的k_start
//修改楼主的代码,让其能定出正确的k_start.
//
//如果没有限制程序的大小,改用静态数组,不用动态数组,
//调用malloc和free函数,有的编译器提示需要stdlib.h

//测试:
//2
//10 -5 -6 3 2 1 -7 6 3 -10 8
//Case 1:
//9 7 8

//测试:
//1
//10 9 -6 -7 3 2 1 -1 -1 -1 9
//Case 1:
//12 4 10

#include<iostream>
#include<string>
using namespace std;

int main()//最大子序列和
{
    int t, n,  max;
    //原代码int *a, *sum_max;
    int a[100001],sum_max[100001];
    int k_start, k_end;
    cin >> t;
    for (int i = 0; i < t; i++)
    {
        cin >> n;
        if (n >= 1 && n <= 100000)
        {
            //原代码a = (int*)malloc(n*sizeof(int));//动态数组
            //原代码sum_max = (int*)malloc(n*sizeof(int));

            //原代码for (int j = 0; j < n; j++)
            for (int j = 1; j <= n; j++)
            {
                cin >> a[j]; //按照原题目,从a[1]到a[n]
            }

            k_start = k_end = 1;  //原代码k_start = k_end = 1;
            sum_max[1] = a[1]; //原代码sum_max[0] = a[0];
            max = sum_max[1]; //原代码max = sum_max[0];
            int tmp_k_start=k_start; //记录临时start

            //原代码for (int k = 1; k < n; k++)
            for (int k = 2; k <= n; k++)
            {
                if (sum_max[k - 1] >= 0)
                {
                    sum_max[k] = a[k] + sum_max[k - 1];
                    if(sum_max[k]<0)
                    {
                       tmp_k_start=k+1; //记录临时start
                    }
                    if (sum_max[k]>max)
                    {
                        max = sum_max[k];
                        k_end = k ; //原代码k_end = k + 1;
                        k_start=tmp_k_start; //这里,临时start发挥作用
                    }
                }
                else
                {
                    sum_max[k] = a[k];
                    if(sum_max[k]<0)
                    {
                       tmp_k_start=k+1; //记录临时start
                    }
                    if (sum_max[k] > max)
                    {
                        max = sum_max[k];
                        k_start = k ; //原代码k_start = k + 1;
                        k_end = k ; //原代码k_end = k + 1;
                        tmp_k_start=k_end; //记录临时start
                    }
                }
            }

            cout << "Case " << i + 1 << ":" << endl;
            cout << max << " " << k_start << " " << k_end << endl;

            if (i < t - 1)
            {
                cout << endl;
            }

            //原代码free(a);
            //free(sum_max); //释放动态内存

        } //if (n >= 1 && n <= 100000)结束
    }//for (int i = 0; i < t; i++)结束

    return 0;
}