求解最大连续子序列并输出子序列
时间: 2024-06-13 15:04:43 浏览: 11
求解最大连续子序列的方法有两种,分别是动态规划和暴力枚举。其中动态规划的时间复杂度为O(n),而暴力枚举的时间复杂度为O(n^2)。下面分别介绍这两种方法的具体实现:
动态规划方法:
1. 初始化sum[]全为0,m初始化指向第一个数,即m=0, n初始化指向第一个数,即n=0
2. 让sum=a,m,n等于指向第一个数也就是等于0
for循环i从1取到n-1:
内部初始化变量b用于存储当前值与前一个值的最大子序列值的和
b与a[i]比较,如果b大:就将b认为当前阶段最大子序列的值,如果b小于:就认为当前阶段最大值为a[i],说明当 前值优于前面最大子序列的值,并且更新m的值等于i
n的值是每次找到最大sum值的下标,因为最大子序列的结束下标sum值一定大于或等于起始下标m的sum值
3. 循环结束后max的值即是最大字段和m,n是最大连续字段和的开始和结束下标。
暴力枚举方法:
1. 初始化变量max用来存储最大值,变量left和right用于存储最大字段和的起始和终止下标
2. for循环i从第1个数到第N个数:
初始化变量b用于存储从i到内层for循环j的的和
for循环j从第i个数到第N个数:
b+=a[j];
判断b和max的值进行取舍如果b>max说明当前找到最大值并且当前最大子序列从i到j,更新left和right指向
3. 当双层for循环结束后max中存储的是最大连续字段的和,left和right分别指向最大字段和的起始和结束位置。
最大连续子序列的输出可以通过输出数组中下标从left到right的元素来实现。
相关推荐
![application/msword](https://img-home.csdnimg.cn/images/20210720083327.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)