算法-最大子序列和

简介: 最大子序列和的问题,数据结构与算法一书分析中给出了四种算法,最优的算法的时间复杂度为O(N), 1 // MaxSubsequenceSum.cpp : 定义控制台应用程序的入口点。 2 // 3 4 #include "stdafx.

最大子序列和的问题,数据结构与算法一书分析中给出了四种算法,最优的算法的时间复杂度为O(N),

 1 // MaxSubsequenceSum.cpp : 定义控制台应用程序的入口点。
 2 //
 3 
 4 #include "stdafx.h"
 5 #include <iostream>
 6 using namespace std;
 7 int MaxSubsequeSum(const int *A,int N)
 8 {
 9     int sumTemp=0;
10     int sumResult=0;
11 
12     for(int index=0;index<N;index++)
13     {
14         sumTemp+=A[index];
15         if(sumResult<sumTemp)
16         {
17             sumResult = sumTemp;
18         }
19         else if(sumTemp < 0)
20         {
21             sumTemp = 0;
22         }
23     }
24     return sumResult;
25 }
26 
27 
28 int _tmain(int argc, _TCHAR* argv[])
29 {
30     int  a[10] = {-1,2,1,-1,1,-3,6,-4,1,-3};
31     cout<<MaxSubsequeSum(a,10)<<endl;
32     return 0;
33 }

算法的正确性分析没有给出过程,分析过程如下:

此算法将整个数组序列分成了不同的子序列,子序列有如下规则

  • 若子序列只有一个元素,那么此元素的值必定为负数
  • 若元素个数n>1,那么第一个元素值sub_array[0]一定为大于0的数,并且最后一个元素sub_array[n-1]必定为小于0的数(如果sub_array[n-1]>=0,因为sum(sub_array[0],...,sub_array[n-2])必定大于等于0,那么sum(sub_array[0],...,sub_array[n-1])>=0,得出sub_array[n-1]不是最后一个元素,矛盾)。
  • 子序列中的最大和值的求出肯定包含第一个元素。

得出最大值有以下两种情况:

  • 子序列中最大值中的最大值,这是上述算法得出的结果。
  • 还有一种可能,最大值可不可能存在两个或者多个相邻子序列中,这里只需要判断两个子序列即可,也就是最大子序列由第一个子序列的结尾部分和第二个子序列组合而成。看下图:第二个子序列最大和值为6,第一个子序列最后一个值为-3,结果为max_sub_array_1_AND_2 = max_sub_array_1 + sub_array_2[n-1]+sub_array_2[n-2]+......其中sub_array_2[n-1]+sub_array_2[n-2]+......>0,但这是不可能的。因为除sub_array_2[0]可能大于|sub_array_2[n-1]|外,其余必定小于|sub_array_2[n-1]|,sub_array_2[n-1]+sub_array_2[n-2]+......必定<0.因此第二种可能是不存在的。


作者: HarlanC

博客地址: http://www.cnblogs.com/harlanc/
个人博客: http://www.harlancn.me/
本文版权归作者和博客园共有,欢迎转载,但未经作者同意必须保留此段声明,且在文章页面明显位置给出, 原文链接

如果觉的博主写的可以,收到您的赞会是很大的动力,如果您觉的不好,您可以投反对票,但麻烦您留言写下问题在哪里,这样才能共同进步。谢谢!

目录
相关文章
|
算法
【算法与数据结构】最大子序列和问题
(转载请注明出处:http://blog.csdn.net/buptgshengod) 1.题目      给定一个数字序列,其中有正有负,确定最大子序列和。用穷举法最好的结果也是时间复杂度O(n²)。后来看到一个聪明的方法,直接使时间复杂度变为O(n)。 2.解法 (1)穷举法        把所有序列都算出来找到最大的。 /* 最大序列和问题的求解,一组数列有正有负
862 0
|
6天前
|
存储 编解码 算法
【多光谱滤波器阵列设计的最优球体填充】使用MSFA设计方法进行各种重建算法时,图像质量可以提高至多2 dB,并在光谱相似性方面实现了显著提升(Matlab代码实现)
【多光谱滤波器阵列设计的最优球体填充】使用MSFA设计方法进行各种重建算法时,图像质量可以提高至多2 dB,并在光谱相似性方面实现了显著提升(Matlab代码实现)
|
9天前
|
传感器 机器学习/深度学习 算法
【使用 DSP 滤波器加速速度和位移】使用信号处理算法过滤加速度数据并将其转换为速度和位移研究(Matlab代码实现)
【使用 DSP 滤波器加速速度和位移】使用信号处理算法过滤加速度数据并将其转换为速度和位移研究(Matlab代码实现)
|
8天前
|
传感器 机器学习/深度学习 算法
【UASNs、AUV】无人机自主水下传感网络中遗传算法的路径规划问题研究(Matlab代码实现)
【UASNs、AUV】无人机自主水下传感网络中遗传算法的路径规划问题研究(Matlab代码实现)
|
6天前
|
机器学习/深度学习 传感器 算法
【高创新】基于优化的自适应差分导纳算法的改进最大功率点跟踪研究(Matlab代码实现)
【高创新】基于优化的自适应差分导纳算法的改进最大功率点跟踪研究(Matlab代码实现)
82 14
|
10天前
|
传感器 算法 数据挖掘
基于协方差交叉(CI)的多传感器融合算法matlab仿真,对比单传感器和SCC融合
基于协方差交叉(CI)的多传感器融合算法,通过MATLAB仿真对比单传感器、SCC与CI融合在位置/速度估计误差(RMSE)及等概率椭圆上的性能。采用MATLAB2022A实现,结果表明CI融合在未知相关性下仍具鲁棒性,有效降低估计误差。
108 15
|
11天前
|
机器学习/深度学习 传感器 算法
基于全局路径的无人地面车辆的横向避让路径规划研究[蚂蚁算法求解](Matlab代码实现)
基于全局路径的无人地面车辆的横向避让路径规划研究[蚂蚁算法求解](Matlab代码实现)
|
10天前
|
机器学习/深度学习 算法 数据安全/隐私保护
基于WOA鲸鱼优化的XGBoost序列预测算法matlab仿真
基于WOA优化XGBoost的序列预测算法,利用鲸鱼优化算法自动寻优超参数,提升预测精度。结合MATLAB实现,适用于金融、气象等领域,具有较强非线性拟合能力,实验结果表明该方法显著优于传统模型。(238字)
|
6天前
|
机器学习/深度学习 运维 算法
【微电网多目标优化调度】多目标学习者行为优化算法MOLPB求解微电网多目标优化调度研究(Matlab代码实现)
【微电网多目标优化调度】多目标学习者行为优化算法MOLPB求解微电网多目标优化调度研究(Matlab代码实现)

热门文章

最新文章