第一种就是纯粹的暴力枚举起始、终点。 O(n^3)
第二种在第一种的基础上先进行初始化，将以第一个元素为起点，所有元素为终点的所有子列和存储在S数组中，所以在第三层循环中计算子列和是直接用S[j]-S[i-1]即可，这是利用了空间去换时间。O(n^2)
第三种也是O(n^2)，但是在第二种的基础上，要先算出非负数所在的下标从而减少计算和的次数，但是效果并不好。
//算法3 O(n^2)
//主要是想算出正数的地方 从而减少算和的次数，但是需要先找出所有的正数int n=0,seq[Max_N]={0};
//1 for positive or 0and 0 for negative
int begin=0,end=0;
long max_sum = NULL;
int len = 0;
int pos_list[Max_N]={0};
void getMaxSubSeq(){if(len==0){//如果全是负数则返回0
max_sum=0;
return;
}else if(len==1){//如果只有一个非负数 返回的就是它
max_sum=seq[pos_list[0]];
return;
}else{//否则我们要对每对儿非负数下标进行计算子列和
for (int j = 0;
j第四种 利用分治法的思想，先算左面，再算右面（都是递归），再从中间开始向两边延伸。O(nlgn)
//算法4
//分治法 O(nlgn)
//此时计算的是A[m,n)的范围内的最大子序列和
int getMaxSumOfSubSeq(int* A,int x,int y){
//递归边界
if(y-x==1)return A[x];
//分治第一步，划分（确定子问题）
int middle = x+(y-x)/2;
//此处不用(x+y)/2的原因是想要使middle更加接近左端点
//分治第二步 递归求解//利用了>?运算符取两者中较大的
int maxOfTwoSides = getMaxSumOfSubSeq(A, x, middle) >?
getMaxSumOfSubSeq(A,middle , y);
//分治第三步 合并 求最终解
int v = 0;
//此处v是用来暂时储存连续从中段开始向两边延伸的连续和
int L=[middle-1],R=A[middle];
//从中间开始
for (int i=middle-1;
i>=x;
i--)
L >?= (v+=A[i]);
v=0;
//重复利用临时变量
for (int i=middle;
i?= (v+=A[i]);
return maxOfTwoSides >? (L+R);
} 第五种， 思路主要是这样的。
在我们用第二种思路时，第二层循环内部要进行比较S[j]-S[i-1]和当前最大和谁大，其实在这个时候，j是一定的，比谁大的本质就是找S[i-1]最小，所以我们不如去维护目前遇到过的最小的S.
int getMSoSS(int* A,int len){
int index_ofMinS = 0;
int S[Max_N];
S[0]=A[0];
//第一步 先算出最小的S在哪里取得
//实验表明，如果S[len-1]是最小的 必须用第二小的才行 所以就不算len-1了
for(int i =1;
i第六种的伪代码描述：在线处理算法 最核心的想法就是当前和如果是负数就不要进行下去 因为无论后面是什么，都相当于在做减法，不会比最大和高。
厉害啦，是在线算法，在线算法就是说，任何时候停止输入，得到的都是当前的正确结果，所以应该是线性的O(n)算法。
int MaxSubseqSum4( int A[], int N )
{int ThisSum, MaxSum;
int i;
ThisSum = MaxSum = 0;
for( i = 0;
i < N;
i++ ) {
ThisSum += A[i];
/* 向右累加 */
if( ThisSum > MaxSum )
MaxSum = ThisSum;
/* 发现更大和则更新当前结果 */
else if( ThisSum < 0 ) /* 如果当前子列和为负 */
ThisSum = 0;
/* 则不可能使后面的部分和增大，抛弃之 */
}
return MaxSum;
}【算法学习笔记|【算法学习笔记】19.算法设计初步 最大子列和问题的三种方法】
推荐阅读
- 人工智能|干货！人体姿态估计与运动预测
- 分析COMP122 The Caesar Cipher
- 技术|为参加2021年蓝桥杯Java软件开发大学B组细心整理常见基础知识、搜索和常用算法解析例题（持续更新...)
- C语言学习(bit)|16.C语言进阶——深度剖析数据在内存中的存储
- Python机器学习基础与进阶|Python机器学习--集成学习算法--XGBoost算法
- 数据结构与算法|【算法】力扣第 266场周赛
- 数据结构和算法|LeetCode 的正确使用方式
- leetcode|今天开始记录自己的力扣之路
- 人工智能|【机器学习】深度盘点（详细介绍 Python 中的 7 种交叉验证方法！）
- 网络|简单聊聊压缩网络