题目集总目录

# 01 - 复杂度 1 最大子列和问题 (20 分)

本题链接

是本次课最后讲到的 4 种算法的实验题，属于基本要求，一定要做；

# 代码

在这里插入图片描述

本题链接

是 2004 年浙江大学计算机专业考研复试真题，要求略高，选做。；

题目大意为找到最大子序列和，以及最大子序列的第一个和最后一个数字。
要注意若有多个最大子序列，则取索引最小的那个

	#include <iostream>
	using namespace std;
	#define N 10002
	int n, x, nowsum, maxsum, l, r, first,last;
	int a[N];
	int main() {
	bool allminus = true;
	cin >> n;
	for(int i = 0; i < n; ++i)
	cin >> a[i];
	maxsum = -1;
	for(int i = 0; i < n; ++i) {
	if (a[i] >= 0)
	allminus = false;
	nowsum += a[i];
	if (nowsum > maxsum && nowsum >= 0) {// 最大，更新 maxsum 和 r
	maxsum = nowsum;
	r = i;
	first = l;
	last = r;
	} else if(nowsum < 0) {
	nowsum = 0;
	l = r = i+1;
	}
	}
	if (allminus) {
	cout << 0 << " " << a[0] << " " << a[n-1] << endl;
	} else cout << maxsum << " " << a[first] << " " << a[last] << endl;
	return 0;
	}

测试点如下，其中 5、6 易错
在这里插入图片描述

本题链接

配合课后讨论题给出这道函数填空题，学有余力、并且会 C 语言编程的你可以尝试一下。你只需要提交一个函数，而不用交如 main 函数之类的其他函数。不会 C 语言的话，就研究一下课后关于二分法的讨论题吧

	#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;
	}

	/* 你的代码将被嵌在这里 */
	Position BinarySearch( List L, ElementType X ) {
	if (L->Last == 0) return NotFound;
	int l, r, mid, ans;
	l = 1, r = L->Last;
	while(l <= r) {
	mid = (l + r) / 2;
	if(L->Data[mid] == X) {
	ans = mid;
	return ans;
	} else if(L->Data[mid] < X) {
	l = mid + 1;
	} else r = mid - 1;
	}
	return NotFound;
	}

测试点如下，其中 5 易错
在这里插入图片描述