PATEST-A1007-题解

START:

for (int i = 0; i < 10; i++)
	{
		cout << i;
		for (int j = 0; j < i; j++)
		{
			cout << " " << j;
		}
		cout << endl;
   }

它在i = 0 j = 0的时候真的不会执行 j中的东西啊！

题目

最大子序列。

• 输入：输入第1行给出正整数 K (<= 100000)；第2行给出K个整数，其间以空格分隔。
• 输出：
  • 最大和小于0时，输出 0还有第一个和最后一个元素。
  • 其他的输出最大和，最大子序列首尾元素。
    • 特别的，如果最大子序列不唯一，输出首位大小最小的。
  • 所有数字之间以空格相分开。

想法

两种解题思路：

1. 三重循环，i j循环控制首尾元素，k循环加元素。

2. 二重循环，首先算出来前缀和，然后利用 sum[i]-sum[j]来算出子序列的和。

   如果，sum[0]放的是第 0 个元素的和，sum[4]放的是第 0 个到第 4 个元素的和。

   那么，sum[4] - sum[0]求出来的即是第 1 个到第 4 个元素的和。

代码

1. 三重循环源代码：

/*
	此代码未通过所有样例。
*/

#include <iostream>
#include <vector>

using namespace std;
vector<int> v;
int main()
{
	int K;
	cin >> K;
	for(int i=0;i<K;i++)
	{
		int d;
		cin >> d;
		v.push_back(d);
	}
	int s, e ;
	long int sum = 0;
	long int maxsum = 0;
	for (int i = 0; i < K; i++)
	{
		for (int j = 0; j < K; j++)
		{
			for (int k = i; k < j; k++)
			{
				sum += v[k];
				if (sum > maxsum)
				{
					maxsum = sum;
					s = i;
					e = j-1;
				}
			}
			sum = 0;
		}
	}
	cout << maxsum << " "<< v[s] <<" " << v[e];
    return 0;
}

2. 二重循环源代码：

#include <iostream>
#include <vector>

using namespace std;
vector<int> v;
vector<int> sum;

int main()
{
	int K;
	cin >> K;
	for(int i=0;i<K;i++)
	{
		int d;
		cin >> d;
		v.push_back(d);
	}//数据存储
    
	int s = 0, e = K-1;
	sum.push_back(0);//放入v[0]
	for (int i = 1; i <= K; i++)
	{
		int _sum;
		_sum = sum[i - 1] + v[i - 1];
		sum.push_back(_sum);
	}//求前缀和
    
	long int maxsum = -9999999;
	for (int i = 0; i <= K; i++)
	{
		for (int j = 0; j < i; j++)
		{
			if (sum[i] - sum[j] > maxsum)
			{
				maxsum = sum[i] - sum[j];
				s = j;
				e = i-1;
			}// end if
		}// end for j
	}//end for i

	
	if (maxsum < 0)
	{
		maxsum = 0;
        s = 0;
        e = K - 1;
	}
	
	
	cout << maxsum << " " << v[s] << " " << v[e];
	
	return 0;
}

思考

这次代码提交了 12 次，对于一些没有考虑到的总结下。

• ···
  int maxsum = 0;
  int s, e;
  ···
  if (sum > maxsum)
  	{
  		maxsum = sum;
  		s = i;
  		e = j-1;
  	}
  ···
  cout << maxsum << " " << v[s] << " " << v[e];

  在写时报段错误，其原因为：如果给出的序列全为负，则 s e无法更新，导致 cout时，使用了未经初始化的内存，所以，应当加入if判断。如下：

  if (maxsum < 0)
  	{
  		maxsum = 0;
          s = 0;
          e = K - 1;
  	}

• 未考虑到 maxsum = 0的情况：

  int maxsum = 0;
  ···
  if (sum > maxsum)
  ···

  写时，得到部分正确的结果，应当将maxsum的值修改为inf。

• 在二重循环的时候，搞反s e的值。

• for (int i = 0; i < K; i++)

  在二重循环的时候，边界值应当为 i-1而非 i。

• for (int i = 0; i < 10; i++)
  {
  	cout << i;
  	for (int j = 0; j < i; j++)
  	{
  		cout << " " << j;
  	}
  	cout << endl;
   }

  它在i = 0 j = 0的时候真的不会执行 j中的东西啊！

END