求最大子列问题 不同方法的复杂度【数据结构初始】

• 通过time.h中的start clock 计算
• • 第一种 最大子列问题的最简单算法，三层循环
  • • 第二种 最大子列问题，简单的优化
    • • 第三种 在线处理

什么是最大子列？
在一个数组中 1 3 2 -1 -7 最大子列就是6
2 -3 1 -4 中 最大子列就是2；但不能是3.
即它本身或者和它相邻的元素的和
首先#include我们利用计算机的时间两个时刻差，计算中间的时间来算算法执行的效率，同产生随机数函数一样需要用到这个头文件，其次需要两个固定的操作
clock_t start, stop;大致的模板如下：

start=clock();
中间插入代码
可以任意补充
stop=clock();
这样就算得了两个时间差
```duration = ((double)(stop - start));

然后通过强制类型转换得出时间差，需要注意的是 咱们每个程序执行的都是非常快的，在单位为tick的条件下，得到值情况都大多都为0，这时候咱们需要做的——————不同的两个算法，循环同样的次数，很巧妙的操作。这时候咱们大致就得到了算法效率！

```cpp

#include
using namespace std;
#include
clock_t start, stop;
int  sum(int* a, int N)
{
	int k; int max=0;
	int b ;
	for (int i = 0; i < N; i++)
	{


		for (int j = i; j < N; j++)
		{
			b = 0;
			for (k = i; k <=j; k++)
			{
				b = a[k] + b;
			}
			if (b > max)
				max = b;
		}
		
	}
	return max;

				 
		
	
}
int main()
{
	int r = -1;

	const int N = 10;
	int c;
	
	int p[N];
	
	for (int i = 0; i < N; i++)
	{
		
		p[i] = r*i;
		r = -r;

	}
	start = clock();
	for (int a = 0; a < 100000; a++)//我们让它执行十万次
	{
		c = sum(p, N);
	}
	stop = clock();
	int m = ((double)(stop - start));
	cout << m << endl;
	cout << c;
	
	
	return 0;

}

大家可以运行一下程序的结果我这边测试的效率是39tick, 最大子列是9

我们比较可以发现，利用三层循环的话，计算一次后舍弃，b=0；然后继续计算，两个数，舍弃，三个数，变得复杂，我们如果计算完不能 不进行舍弃，直接比较+更新，那么算法会简单一点。

#include
using namespace std;
#include
time_t start, stop;
int sum(int* p, int N)
{
	int sum = 0; int max=0;
	for (int i = 0; i < N; i++)
	{
		sum = 0;
		for (int j = i; j < N; j++)
		{
			sum = sum + p[j];
			if (sum > max)
				max = sum;
		}
	}
	return max;
		
		

}
int main()
{
	const int C  = 10;
	int r = -1;
	int m = 0;
	int a[C];
	for (int i = 0; i < 10; i++)
	{
		a[i] = r * i;
		r = -r;
	}
	start = clock();
	for(int i=0;i<100000;i++)
	 m = sum(a, C);
	stop = clock();
	int c = double(stop - start);
	cout << c << endl;
	cout << m;


	
}

时间效率
同样是9但只需要12

咱们从右向左累加，每次累加先保存起来，比较和MAX的大小，然后再把累加的值和0比较 如果小于0 那么没有存在的必要 ，跳过这个，令初始值为0，数组往后加，这样巧妙的方法只需要一个循环可以解决，大家可以自己举例子试试这个算法的巧妙之处

#include
#include
using namespace std;
time_t start, stop;
double sum(int* p,int N)
{
	int now = 0; int max = 0;
	for (int i = 0; i < N; i++)
	{
		now = now + p[i];
		if (now > max)
			max = now;
		else if (now < 0)
			now = 0;

	}
	return max;
}
int main()
{
	int a[10];
	int r = -1;
	int m = 0;
	for (int i = 0; i < 10; i++)
	{
		a[i] = r * i;
		r = -r;
	}
	start = clock();
	for (int i = 0; i < 100000; i++)
m = sum(a, 10);
	stop = clock();

	int b = double(stop - start);
	cout << b << endl;
	cout << m;


}

这里甚至只需要3tick就可以完成，现在大家可以理解数据结构和算法，给程序带来的好处了吗，需要注意的是，算法越简单，对于读程序的人来说 是越难理解的事，有时候斟酌损益需要大家认真考虑！