#数据结构 Record One#
1.
以最大子列和问题引出“分治法”和“在线处理法”两种算法，下面请先看题目：
01-复杂度1 最大子列和问题（20 分）
给定K个整数组成的序列{N1,N2, ..., NK }，“连续子列”被定义为{ Ni,Ni+1, ..., Nj }，其中 1≤i≤j≤K。“最大子列和”则被定义为所有连续子列元素的和中最大者。例如给定序列{ -2, 11, -4, 13, -5, -2 }，其连续子列{ 11, -4, 13 }有最大的和20。现要求你编写程序，计算给定整数序列的最大子列和。
本题旨在测试各种不同的算法在各种数据情况下的表现。各组测试数据特点如下：
数据1：与样例等价，测试基本正确性；数据2：102个随机整数；数据3：103个随机整数；数据4：104个随机整数；数据5：105个随机整数；
输入格式:
输入第1行给出正整数K (≤100000)；第2行给出K个整数，其间以空格分隔。
输出格式:
在一行中输出最大子列和。如果序列中所有整数皆为负数，则输出0。
输入样例:
6
-2 11 -4 13 -5 -2
输出样例:
20
看完题目后我们马上会有一个思路：就是用一个双重循环将数列里的数一个一个加起来，用ThisSum记录，每加一个比较一下ThisSum和MaxSum，如果ThisSum比MaxSum大的话，那么我们就将ThisSum赋给MaxSum，代码如下：
#include <iostream>
using namespace std;
int main(){
int N;
cin>>N;
int arr[N];
for( int i = 0 ; i < N ; i++ ){
cin>>arr[i];
}
int Thismax , Maxsum = 0;
for( int i = 0 ; i < N ; i++ ){
Thismax = 0;
for( int j = i ; j < N ; j++ ){
Thismax += arr[j];
if(Thismax>Maxsum){
Maxsum = Thismax;
}
}
}
cout<<Maxsum<<endl;
return 0;
}
我们可以算出这个算法的时间复杂度是O(n^2)，那么还有比这个时间复杂度更小的算法吗，答案是肯定的！
假设此时数列有6个数，分别为-2 11 -4 13 -5 -2，将这个数列分为-2 11 -4和13 -5 -2两部分，分别求出第一个、第二个数列的最大和然后将两个和相加，比较这三个数的大小，最大值就是我们要的结果，那么第一部分的最大和如何求呢，将第一部分的数列在分为两部分，分别求解这两部分，相信你已经发现，这其实就是将原问题分解为几个规模较小但是类似于原问题的子问题，从中我们就可以得出”分治法“的思想：
分治法：分治法采用了递归的结构，将原问题分成几个规模较小但是类似于原问题的子问题，通过递归的方法再来求解这些小问题，然后将子问题的解合并起来建立原问题的解，分治法在每层递归时都有三个步骤：
分解：将原问题分解成若干个小问题，这些子问题是原问题的规模较小的实例
解决：解决这些子问题，通过递归的方式求解子问题，直到问题的规模足够小，可以直接求解
合并：将这些子问题的解合并成原问题的解
下面代码：
/*分治法求最大子列和问题*/
#include <iostream>
using namespace std;
//三个数中返回最大的那一个
int Max(int A , int B , int C){
return A>B ? A>C?A:C : B>C?B:C;
}
//递归分治法
int DivideAndConquer( int List[] , int Left , int Right ){
int Maxleftsum , Maxrightsum;
int MaxleftBordersum , MaxrightBordersum;
int LeftBordersum , RightBordersum;
if(Left==Right){//递归的终止条件，子列只有一个数字
if(List[Left]>0) return List[Left];
else return 0;
}
int center , i;
/*开始"分"*/
center = (Left+Right)/2;
/*递归求两边的最大子列和*/
Maxleftsum = DivideAndConquer( List , Left , center );
Maxrightsum = DivideAndConquer( List , center+1 , Right);
/*下面是跨分界线的最大子列和*/
LeftBordersum = 0 ; MaxleftBordersum = 0;
for( i = center ; i >= Left ; i-- ){//从中间往左扫描
LeftBordersum += List[i];
if( LeftBordersum>MaxleftBordersum){
MaxleftBordersum = LeftBordersum;
}
}//扫描结束
RightBordersum = 0 ; MaxrightBordersum = 0;
for( i = center+1 ; i <= Right ; i++ ){//从中间往右扫描
RightBordersum += List[i];
if(RightBordersum>MaxrightBordersum){
MaxrightBordersum = RightBordersum;
}
}//扫描结束
/*返回三个中最大的那一个(返回"治"的结果)*/
return Max(Maxleftsum , Maxrightsum , MaxleftBordersum+MaxrightBordersum);
}
int MaxSubseqSum3( int List[] , int N ){
return DivideAndConquer(List , 0 , N-1);
}
//测试
int main(){
int N;
cin>>N;
int arr[N];
for( int i = 0 ; i < N ; i++ ){
cin>>arr[i];
}
int a = MaxSubseqSum3(arr,N);
cout<<a;
return 0;
}
此时算法的时间复杂度问为O(n*logn)级别的，那么我们还有比O(n*logn)更加快速的方法吗？请看下面
先上代码了
/*在线处理法求最大子列和问题*/
#include <iostream>
using namespace std;
int MaxSubseqSum4( int List[] , int N ){
int ThisMaxSum = 0 , MaxSum = 0;
for( int i = 0 ; i < N ; i++ ){
ThisMaxSum += List[i];
if(ThisMaxSum>MaxSum){
MaxSum = ThisMaxSum;
}
else if(ThisMaxSum<0){
ThisMaxSum = 0;
}
}
return MaxSum;
}
//测试
int main(){
int N;
cin>>N;
int arr[N];
for( int i = 0 ; i < N ; i++ ){
cin>>arr[i];
}
int a = MaxSubseqSum4(arr,N);
cout<<a;
return 0;
}此时代码中只有一重循环，很显然时间复杂度是O(n)级别的，它的基本思想是将数列中的数一个一个加起来，用ThisSum记录，每加一次判断一次ThisSum和MaxSum的大小，之后判断ThisSum是否小于零，如果小于零则说明ThisSum无法使后面相加的数列增大，则将此时的ThisSum抛弃掉（也就是置为零），这就是“在线处理法”。
2.
二分法 直接上代码（函数部分实现）：
#include <iostream>
using namespace std;
#define MAXSIZE 10
#define NotFound 0
typedef int ElementType;
typedef int Position;
typedef struct LNode*List;
struct LNode{
ElementType Data[MAXSIZE];
Position Last;
};
Position BinarySearch( List L , ElementType X ){
if(L->Last){
int left = 1 , right = L->Last;
while(left<=right){
int Mid = (left+right)/2;
if(L->Data[Mid]==X){
return Mid;
}
else if(X>L->Data[Mid]){
left = Mid+1;
}
else if(X<L->Data[Mid]){
right = Mid-1;
}
}
}
return NotFound;
}
