目录
1.最大子列和问题
2. Maximum Subsequence Sum
3.二分查找（函数填空）
1.最大子列和问题
代码概述：
1.三种方法：穷举、分治、在线处理 2.穷举法：计算所有可能子列和，比较大小 3.分治法：分解问题，求左边最大子列和、右边最大子列和、跨越边界最大子列和三者中的最大。 4.在线处理：每输入一次，进行一次即时处理。
注意：
1.分治法中子问题最小为“一个元素”，即终止条件left==right。 2.分治法计算跨越边界的子列和时注意，一个从中间向左边扫描left←mid，一个从中间向右边扫描mid+1→right。 3.分治法初始头尾是0和k-1（数组下标范围）。
代码：
#include<iostream>
using namespace std;
//穷举
void MaxSeq2(int a[], int n)
{
int thissum, maxsum=0;
for(int i=0; i<n; i++){
thissum = 0;
for(int j=i; j<n; j++){
thissum += a[j];
if(thissum > maxsum)
maxsum = thissum;
}
}
cout<<maxsum;
}
//分治法
int Max3(int a, int b, int c){
int max;
int m = a>b ? a :b;
max = c>m ? c : m;
return max;
}
int MaxSeq3(int a[], int left, int right)
{
int MaxLeftSum=0, MaxRightSum=0;
int mid;
if(left==right){
if(a[left]>0)
return a[left];
else return 0;
}
mid = (left + right)/2;
MaxLeftSum = MaxSeq3(a, left,mid);
MaxRightSum = MaxSeq3(a, mid+1,right);
//跨越边界最大子列和
int MaxLeftBorder=0, MaxRightBorder=0;
int ThisLeftBorder=0, ThisRightBorder=0;
for(int i=mid; i>=left; i--){
ThisLeftBorder += a[i];
if(ThisLeftBorder > MaxLeftBorder)
MaxLeftBorder = ThisLeftBorder;
}
for(int i=mid+1; i<=right; i++){ //mid+1，不是mid
ThisRightBorder += a[i];
if(ThisRightBorder > MaxRightBorder)
MaxRightBorder = ThisRightBorder;
}
//每次分治结果输出
//cout<<MaxLeftBorder<<"+"<<MaxRightBorder<<" 左:"<<MaxLeftSum<<" 右:"<<MaxRightSum<<endl;
return Max3(MaxLeftSum,MaxRightSum,MaxRightBorder+MaxLeftBorder);
}
//在线处理
void MaxSeq4(int a[], int n)
{
int thissum=0, maxsum=0;
for(int i=0; i<n; i++){
thissum += a[i];
if(thissum < 0) thissum = 0;
else if(thissum > maxsum) maxsum = thissum;
}
cout<<maxsum;
}
int main()
{
int k;
cin>>k;
int a[k];
for(int i=0; i<k; i++){
cin>>a[i];
}
//MaxSeq2(a, k);
//cout<<MaxSeq3(a,0,k-1); //k-1，不是k
MaxSeq4(a, k);
return 0;
}
2. Maximum Subsequence Sum
单词整理：
sequece：序列 integer：整数 subsequence：子列output the one with the smallest indices i and j：输出下标最小的数，而
不是输出下标！！
概述：
核心：在线处理。 特殊情况：含0、负数。
注意：
输出
不是数组下标！！而是
数值！！ 特例1：含0和 负数：输出0 0 0。特例2：全为负数：输出 0 开头数字 结尾数字。
因此maxsum初始化为负，而不能是0。
代码：
#include <iostream>
using namespace std;
void MaxSeq(int a[], int n)
{
int thissum=0, maxsum=-1;//maxsum设置为-1
int maxstart=0, maxstop=0;
int thisstart=0;
for(int i=0; i<n; i++){
thissum += a[i];
if(thissum < 0 && i<n-1){
thissum=0;
thisstart =i+1;
}
else if(thissum>maxsum){
maxsum = thissum;
maxstart = thisstart;
maxstop = i;
}
}
if(maxsum<0){
cout<<0<<" "<<a[0]<<" "<<a[n-1];
}else
cout<<maxsum<<" "<<a[maxstart]<<" "<<a[maxstop];
}
int main()
{
int k;
cin>>k;
int a[k];
for(int i=0; i<k; i++){
cin>>a[i];
}
MaxSeq(a,k);
return 0;
}
3.二分查找（函数填空）
概述：
核心：二分法。两个函数： ReadInput()输入据到L中 ；BinarySearch( L, X )二分法在L中查找X。
注意：
运行需要ReadInput函数，但不需要提交！！提交
BinarySearch函数即可！！！否则编译错误！！LNode为结构体名，List为结构体指针，相当于LNode。 函数返回值为结构体指针List，
指针变量需要赋初值，避免随机地址指向系统工作区间。（使用malloc或者new分配出一个新空间并指向）
代码：
#include <stdio.h>
#include <stdlib.h>
#define MAXSIZE 10
#define NotFound 0
typedef int ElementType;
typedef int Position;
typedef struct LNode *List;
struct LNode {
ElementType Data[MAXSIZE];
Position Last; /* 保存线性表中最后一个元素的位置 */
};
List ReadInput(); /* 裁判实现，细节不表。元素从下标1开始存储 */
Position BinarySearch( List L, ElementType X );
int main()
{
List L;
ElementType X;
Position P;
L = ReadInput();
scanf("%d", &X);
P = BinarySearch( L, X );
printf("%d\n", P);
return 0;
}
/* 上述为题目*/
// ReadInput()不需要提交！但运行需要！
List ReadInput(){
int n;
scanf("%d",&n);
List L1 = (List)malloc(sizeof(LNode));//malloc分配空间，强制类型转换为List
// List L1 = new LNode;
L1->Last = n;
for(int i=1; i<=5;i++)
scanf("%d",&L1->Data[i]);
return L1;
}
//程序填空题 需要提交的函数：
Position BinarySearch( List L, ElementType X ){
Position left, right, mid;
left = 1;
right = L->Last;
while( left<=right ){
mid = (left + right) / 2;
if( X == L->Data[mid] ) return mid;
else if( X > L->Data[mid] ) left = mid+1;
else right = mid-1;
}
return NotFound;
}
