算法第二章上机实践报告
2021-03-19 03:24
标签：时间 了解 字段 最大 编写 分析 htm 算法 定义 1.实践题目：最大子列和问题 2.问题描述： 给定K个整数组成的序列{ N1, N2 , ..., NK}，“连续子列”被定义为{ N?i , Ni+1 ,..., Nj}，其中 1≤i≤j≤K。“最大子列和”则被定义为所有连续子列元素的和中最大者。例如给定序列{ -2, 11, -4, 13, -5, -2 }，其连续子列{ 11, -4, 13 }有最大的和20。现要求你编写程序，计算给定整数序列的最大子列和。 3.算法描述： 运用分治法，分析问题得出最大子列和的分布有三种情况：（1）左子序列；（2）右子序列；（3）位于中部的横跨左右的子序列。 递归结束的条件：left=right,若left>0,则返回a[left],否则返回0。 依次得出左子序列的最大子列和，右子序列的最大子列和，横跨左右的子序列的最大子列和，并比较得出最大者。 4.算法时间及空间复杂度分析： 设用T(n)表示解决该问题所需的时间，分解子问题所需时间为O(1),对该问题分成2个规模为n/2的子问题则所需时间为2T(n/2),合并子问题所需时间为O(n)； {O(1) 则T(n)={2T(n/2)+O(n) 由于a=2, b=2, d=1,得到d=logb a 所以时间复杂度为O(nlogn) 5.心得体会： 刚开始写的时候发现了一个问题，如： int leftmaxsum=Maxsum(a, left, mid);//左序列最大字段和 这是正确的写法，以下是我刚开始写的错误写法 int leftmaxsum=Maxsum(a, left, mid-1);//左序列最大字段和 这会导致当left=0，right=1时，mid-1=-1越界的情况 同时也在网上了解到动态规划的方法，时间复杂度为T(n)=O(n),在此题的限制下两者差不太多 算法第二章上机实践报告 标签：时间 了解 字段 最大 编写 分析 htm 算法 定义 原文地址：https://www.cnblogs.com/Sullivan2333/p/13765638.html
int rightmaxsum=Maxsum(a, mid+1, right);//右序列最大字段和
int rightmaxsum=Maxsum(a, mid, right);//右序列最大字段和