算法学习记录

总和区间最大问题

给定一个实数序列，设计一个算法，找到一个总和最大的区间。

方法1

三层循环，第一个循环遍历开始位置，第二层循环遍历结束位置，第三层循环把开始位置到结束位置的所有数相加，记录最大的。算法复杂度O(N^3^)

方法2

两层循环，第一层循环为开始位置p，第二层循环维护一个变量S(p,q)，意义是从p到q的和，计算S(p,q+1)时只需将S(p,q)加上（q+1）,储存一个最大值变量，如果S（p,q）>Max，记录相应参数，更新Max。复杂度O(N^2^)

方法3

分治思想。具体略，复杂度为O（N Log N）

方法4

改进方法2，正反扫描两遍。找到第一个为正的实数，利用方法2，可以找到一个右边界，但是不知道左边界，因此从右边界开始向左扫描一遍同理可以得到左边界，因此复杂度为O（N）。

区间和等于一个数

方法1

外层循环设置起始位置，内层循环可以计算从起始位置到序列末尾任何一个数为区间右端点的区间和，O（N^2^）

方法2

方法1其实做了重复计算，计算了S（1,q）后，S（p,q）= S (1,q) - S (1,p-1),S(1,q)可以构建嘻哈表。O(N)

二维矩阵找和最大的矩形区域

假设行列号从0开始，设s(i,j)为第i行前j个数字之和，依据之前的算法，复杂度为O（m*n），设S（p,q）为矩阵中以（0,0）位左上角点 ，以（p,q）为右下角点的矩形数字之和，S（p,q）= S（p-1,q）+s(p,q)复杂度为O（m*n）,得到所有S（p,q）并找出最大的S（p1,q1）,当做矩形的右下角点，与一维数组的思路一样，再遍历一遍得到矩形的左上角点，p0q0, 矩形的面积为 S（p1,q1）- S(p1,q0) - S(p0,q1) + S（p0,q0）,找到最大的。复杂度也为O（m*n）。总体来说复杂度为O（m*n）,只是需要较大的空间。

递归问题

全排列

按照字典序输出自然数 1到 n所有不重复的排列，即 n 的全排列，要求所产生的任一数字序列中不允许出现重复的数字。 假设n取1到9.

#include<stdio.h>
/*
对当前的位置进行深度优先搜索，找到每个可以填进去的数进行尝试。搜完了这个位置以后回溯继续搜。
*/
int n;
int line[10]; //排列
bool visit[10];//标记是否使用

void print()
{
	for(int i=1; i<=n; ++i)
		printf("%d ", line[i]);
	printf("\n");
	return ;
}

void dfs(int x)
{
	if(x>n)
	{
		print(); 搜索到叶子节点，打印。
	}
	for(int i=1; i<=n; ++i)
	{
		if(visit[i]) continue;//objective 1 如果这个数用过了怎么办？
		else
        {
          visit[i] = 1;
          line[x]=i; //第x层赋值
          dfs(x+1); //第x+1层
          visit[i]=0; 不能再向下搜索，开始回溯，删去标记。
        }
	}
	return;
}

int main()
{
	scanf("%d",&n);
	dfs(1); 从搜索树的第一层开始
	return 0;
}