商洛建设公司网站,好看的模板网站建设,广州一建筑外墙脚手架坍塌,php开发网站后台题目详情#xff1a;
给定K个整数组成的序列{ N1, N2, ..., NK }#xff0c;“连续子列”被定义为{ Ni, Ni1, ..., Nj }#xff0c;其中 1≤i≤j≤K。“最大子列和”则被定义为所有连续子列元素的和中最大者。例如给定序列{ -2, 11, -4, 13, -5, -2 }#xff…题目详情
给定K个整数组成的序列{ N1, N2, ..., NK }“连续子列”被定义为{ Ni, Ni1, ..., Nj }其中 1≤i≤j≤K。“最大子列和”则被定义为所有连续子列元素的和中最大者。例如给定序列{ -2, 11, -4, 13, -5, -2 }其连续子列{ 11, -4, 13 }有最大的和20。现要求你编写程序计算给定整数序列的最大子列和。
本题旨在测试各种不同的算法在各种数据情况下的表现。各组测试数据特点如下
数据1与样例等价测试基本正确性数据2102个随机整数数据3103个随机整数数据4104个随机整数数据5105个随机整数
输入格式:
输入第1行给出正整数K (≤100000)第2行给出K个整数其间以空格分隔。
输出格式:
在一行中输出最大子列和。如果序列中所有整数皆为负数则输出0。
输入样例:
6
-2 11 -4 13 -5 -2输出样例:
20
主要思路
方法一贪心
主要思路就是维系当前连续的子列和大于0如果小于0就清零重新计算如果比maxSum大就顶替
代码实现
#include stdio.h
#define MAX_NUM 100005
int NUM[MAX_NUM];
int main() {int K;scanf(%d, K);for(int i 0; i K; i) {scanf(%d, NUM[i]);}int maxSum 0;int sum 0;for(int i 0; i K; i) {sum NUM[i];if(sum 0) { //sum小于0说明这是连续的子列和不是最大将sum清零sum 0;}if(sum maxSum) {maxSum sum;}}printf(%d, maxSum);return 0;
}
方法二 递归分治
1. 将序列从中间分为左右两个序列
2. 递归求得两子列的最大和sumLeft与sumRight
3.从中分点向左右扫描找到跨过分界线的最大子列和sumMiddle
4.取最大值
实际操作时递归三部曲
1.参数与返回值
参数num数组
返回当前子列和最大值
2.终止条件
左右端点重合
3.单层递归逻辑
单纯左侧与单纯右侧简单难的是跨中间点
跨中间点其实也用到了贪心的想法即分成两部分分别找左[left, middle)与右[middle 1, right]的最大值然后加起来就是跨中间点最大值
第一次写错误
比较容易混的在于左右边界的裁决
在单层递归逻辑判断中左半部分是从left到middle不是middle-1
跨过分界点的部分是分别从中线middle到left右半部分是从middle1到right
代码实现
#include stdio.h
#define MAX_NUM 100005
int NUM[MAX_NUM];
int FindMAX(int a, int b, int c) {int max 0;if(a b) {if(a c) max a;else max c;}else {if(b c) max b;else max c;}return max;
}
int crossMax(int* num, int left, int middle, int right) {int leftSideMaxSum 0, leftSideSum 0;int rightSideMaxSum 0, rightSideSum 0;for(int i middle; i left; i--) { //从中线向左扫描leftSideSum num[i];if(leftSideSum leftSideMaxSum) leftSideMaxSum leftSideSum;}for(int i middle 1; i right; i) { //从中线向右扫描rightSideSum num[i];if(rightSideSum rightSideMaxSum) rightSideMaxSum rightSideSum;}return leftSideMaxSum rightSideMaxSum;
}
int recursion(int* num, int left, int right) {//递归终止条件左右下标相等如果当前这个数字大于0返回这个数字否则返回0即连续子列里不包含这个数字if(left right) {if(num[left] 0) return num[left];else return 0;}//单层递归逻辑int middle (left right) / 2;int leftSideMaxSum recursion(num, left, middle); //左半部分右边界是middle不用减去1int rightSideMaxSum recursion(num, middle 1, right);int crossMaxSum crossMax(num, left, middle, right);return FindMAX(leftSideMaxSum, rightSideMaxSum, crossMaxSum);
}
int main() {int K;scanf(%d, K);for(int i 0; i K; i) {scanf(%d, NUM[i]);}int ret recursion(NUM, 0, K - 1);printf(%d, ret);return 0;
}
