FIrst:无限制最大子段和问题 时间复杂度:

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
long long f[N];

int main(){
	int n;
	scanf("%d",&n);
	long long res=-0x3f3f3f3f3f3f3f3f;
	for(int i=1;i<=n;i++){
		long long x;
		scanf("%lld",&x);
		f[i]=max(f[i-1],(long long)0)+x;
		res=max(res,f[i]);
	}
	printf("%lld\n",res);
	
	return 0 - 0;
}

Second:子段长度不大于m的最大子段和问题 时间复杂度:

#include<bits/stdc++.h>
using namespace std;
const int N=3e5+10;
int n,m;
long long sum[N];

int main(){
    scanf("%d %d",&n,&m);
    for(int i=1;i<=n;i++){
        long long x;
        scanf("%lld",&x);
        sum[i]=x+sum[i-1];
    }
    deque<long long> q;
    q.push_back(0);
    long long res=-0x3f3f3f3f3f3f3f3f;
    for(int i=1;i<=n;i++){
        while(q.size()&&i-q.front()>m) q.pop_front();
        res=max(res,sum[i]-sum[q.front()]);
        while(q.size()&&sum[q.back()]>=sum[i]) q.pop_back();
        q.push_back(i);
    }
    printf("%lld\n",res);
    
    return 0 - 0;
}

 Third:长度不小于m的最长子段和问题 时间复杂度:

#include<bits/stdC++.h>
using namespace std;
const int N=2e5+10;
int sum[N],f[N],g[N];

int main(){
	int n,m;
	scanf("%d %d",&n,&m);
	for(int i=1;i<=n;i++){
		int x;
		scanf("%d",&x);
		f[i]=max(f[i-1],0)+x;
		sum[i]=sum[i-1]+x;
	}
	int res=-0x3f3f3f3f;
	for(int i=1;i+m-1<=n;i++){
		g[i]=max(f[i-1],0)+sum[i+m-1]-sum[i-1];
		res=max(g[i],res);
	}
	printf("%d\n",res);
	
	return 0 - 0;
}

Foruth:环状最大子段和问题 时间复杂度:

 1.将序列倍长，就可以做一遍长度不大于m的最大子段和

 2.先正着求一遍最大子段和，考虑子段是否过端点，过端点就取反，然后求一个最小子段和，不过端点就没有影响。

Fifth:环状最大两段子段和 时间复杂度: / 

 考虑破环成链，枚举破坏的断点，在链上求最大两段子段和；维护一个为以结尾的最大子段和，一个为以开头的最大子段和；(其实就是倒着求一遍)复杂度；

 对于答案可能有的所有情况，一种是有一段跨过了端点，另一种是没有跨过端点；所以可以先求一遍两段最大子段和，再对整个序列取反，再求一遍(这时其实就是求出两段的最小子段和，用总和减去后就是跨过端点的两段最大子段和)，这时把两种情况取一个；

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+10;
int s[N],front[N],back[N];

int main(){
	int n;
	scanf("%d",&n);
	for(int i=1;i<=n;i++) scanf("%d",&s[i]);
	memset(front,-0x3f,sizeof(front)); 
	memset(back,-0x3f,sizeof(back));
	int sum1=-2e9,sum2=-2e9,sum=0;
	for(int i=1;i<=n;i++) front[i]=max(front[i-1],0)+s[i];
	for(int i=1;i<=n;i++) front[i]=max(front[i-1],front[i]);
	for(int i=n;i>=1;i--) back[i]=max(back[i+1],0)+s[i];
	for(int i=n;i>=1;i--) back[i]=max(back[i+1],back[i]);
	for(int i=1;i<n;i++) sum1=max(sum1,front[i]+back[i+1]);
	int cnt=0;
	for(int i=1;i<=n;i++){
		if(s[i]>0) cnt++;
	}
	if(cnt<=1){
		printf("%d\n",sum1);
		return 0 - 0;
	}
	memset(front,-0x3f,sizeof(front));
	memset(back,-0x3f,sizeof(back));
	for(int i=1;i<=n;i++) sum+=s[i],s[i]=-s[i];
	for(int i=1;i<=n;i++) front[i]=max(front[i-1],0)+s[i];
	for(int i=1;i<=n;i++) front[i]=max(front[i-1],front[i]);
	for(int i=n;i>=1;i--) back[i]=max(back[i+1],0)+s[i];
	for(int i=1;i<n;i++) sum2=max(sum2,front[i]+back[i+1]);
	sum2=sum+sum2;
	int res=max(sum1,sum2);
	printf("%d\n",res);
	
	return 0 - 0;
}

@[TOC]java代码求解最大子段和问题

什么是最大子段和问题

给定一个数组(元素已知)，元素由正整数，负整数两种元素组成，现在求该数组中从哪个位置到哪个位置对应元素所组成的子段和最大，这个子段和就叫做最大子段和。

分析问题(分治思想)

最大子段和不是在“前半段”（a[0] ~ a[mid]）就是在“后半段”a[mid+1] ~ a[a,length-1],要么就是由“前半段部分元素和后半段部分元素连接起来a[i] ~ a[j]所构成（其中i(从mid ~ 0)，j(从mid+1) ~ (a.length -1);”
就以数组a[] = {-1,3,2}为例

前半段从-1 ~3 后半段从2 ~ 2（也就是它本身） DSZ就指的是前半段和后半段所连接的“累加和最大的”子段和
之后我们可以判断这三个值的大小 从而得出当前数组的最大子段和

发现捷径

当数组长度为2时可以比较a,b,a+b三个数的大小 从而选出最大值即为最大子段和

当数组长度大于2时 需递归调用方法将数组划分为长度等于2的小数组，逐步得到所要求数组的最大子段和。

因为当将数组划分到长度等于2的时候对应的小长度数组的最大子段和可以轻松的求解出来，进而一步步向所求数组一步步靠拢进而得到最终的最大子段和。

if(mid == 0){
			x = a[0];
			y = a[1];
			z = x + y;
			if(x > y){
				max = x;
			}
			else max = y;
			if(max > z){
				max = max;
			}
			else {max = z;}
		return max;
		}

定义一个DSZ方法，用于返回当前数组前半段和后半段连接所构成的“累加和最大的”子段和

public static int DSZ(int a[]){
		int mid = (a.length-1)/2;
		int H = a.length;
		int i,j,max,x,y,z,L,D;
		if(H%2 != 0){
			L = mid+1;
			D = mid ;
		}
		else {
			L = mid +1;
			D = mid +1; 
		}
		int[] d = new int[L];
		int[] e = new int[D];
		for(max = 0,i = mid,j = 0;i >=0;i--,j++){
			max += a[i];
			d[j] = max;
		}
		for(max = 0,i = (mid+1),j = 0;i < a.length;i++,j++){
			max += a[i];
			e[j] = max;
		}
		x = mid - ZDS(d);           
		y = mid +ZDS(e)+1;
		for(max = 0,i = x;i <= y;i++){
			max += a[i];
		}
		return max;
	}

定义ZDS（最大数）方法用于辅佐DSZ方法求出前半段和后半段“累加和最大”的子段和

public static int ZDS(int a[]){
		int max,i,j = 0;
		for(i = 0,max = 0;i < a.length;i++){
			if(max < a[i]){
				max = a[i];
			}
		}
		for(i = 0;i < a.length;i++){
			if(max == a[i]){
				j = i;
			}
		}
	return j;
	}

排版方法

import java.util.Scanner;
public class ZDZD4{
	public static void main(String[] args){
		System.out.println("请输入数组元素并用逗号隔开:");
		Scanner s1 = new Scanner(System.in);
		String str = s1.next().toString();
		String[] b = str.split(",");
		int[] a = new int[b.length];
		for(int j = 0;j < a.length;j++){
			a[j] = Integer.parseInt(b[j]);
			System.out.print(a[j]+" ");
		}
		System.out.println();
		System.out.print("该数组的最大子段和为:"+ZDZD1(a));
	}
	public static int ZDZD1(int a[]){
		int i,j,x,v,max,y = 0,z = 0,n = 0,m = 0,H,L,D,t,q;
		int mid = (a.length-1) / 2;
		int O = a.length;
		if(O == 1){
			return a[0];
		}
		else if(O%2 != 0){
			L = mid+1;
			D = mid ;
		}
		else{
			L = mid +1;
			D = mid +1; 
		}
		int[] b = new int[L];
		int[] c = new int[D];
		if(mid == 0){
			x = a[0];
			y = a[1];
			z = x + y;
			if(x > y){
				max = x;
			}
			else max = y;
			if(max > z){
				max = max;
			}
			else {max = z;}
		return max;
		}
		else {	
			x = DSZ(a);
			for(i = 0;i <= mid ;i++){
				b[i] = a[i];
			}
			for(v = mid+1,j= 0;v < a.length;v++){
				if(a[v] != 0){
					c[j] = a[v];
					j++;
				}
			}
			n = ZDZD1(b);
			m = ZDZD1(c);
			if(n > m){
				max = n;
			}
			else {max = m;}
			if(max > x){
				max = max;
			}
			else {max = x;}
			return max;
		}
	}
	public static int DSZ(int a[]){
		int mid = (a.length-1)/2;
		int H = a.length;
		int i,j,max,x,y,z,L,D;
		if(H%2 != 0){
			L = mid+1;
			D = mid ;
		}
		else {
			L = mid +1;
			D = mid +1; 
		}
		int[] d = new int[L];
		int[] e = new int[D];
		for(max = 0,i = mid,j = 0;i >=0;i--,j++){
			max += a[i];
			d[j] = max;
		}
		for(max = 0,i = (mid+1),j = 0;i < a.length;i++,j++){
			max += a[i];
			e[j] = max;
		}
		x = mid - ZDS(d);           
		y = mid +ZDS(e)+1;
		for(max = 0,i = x;i <= y;i++){
			max += a[i];
		}
		return max;
	}
	public static int ZDS(int a[]){
		int max,i,j = 0;
		for(i = 0,max = 0;i < a.length;i++){
			if(max < a[i]){
				max = a[i];
			}
		}
		for(i = 0;i < a.length;i++){
			if(max == a[i]){
				j = i;
			}
		}
	return j;
	}
}

前言

子序列之和最大，即最大子段和问题(Maximum Interval Sum)（有时也称LIS）

子序列：[A1,A2,…,An] 的子序列: [Ai,Aj] ,其中i<=j, 1 <= i,j <= n

求和：[A1,A2,…,An] 求和 = A1 + A2 + … + An

举例

数组：5 4 -1 7 8
方案1：遍历，求sum值，然后比大小
	5					sum = 5
	5 4					sum = 9
	5 4 -1				sum = 8
	5 4 -1 7		    sum = 15
	5 4 -1 7 8			sum = 23

	  4					sum = 4
	  4 -1				sum = 3
	  4 -1 7			sum = 10
	  4 -1 7 8			sum = 18
	   
		-1				sum = -1
		-1 7			sum = 6
		-1 7 8			sum = 14
		   
		   7			sum = 7
		   7 8			sum = 15
		   
			 8			sum = 8

改进方案1：
	1. 每一次遍历都可以使用上次的计算值 + 下一个元素
	2. i++ 就清零，需要重启计算

方案1：穷举

1. 第一层和第二层 是 进行穷举所有子序列

2. 第三次是求 子序列的累加和

	    public int maxSubArray2(int[] nums) {
	    	if(nums == null || nums.length == 0){
	    		return 0;
	    	}
	    	int len = nums.length;
	    	if(len == 1){
	    		return nums[0];
	    	}
	    	// 所有的和最大值，默认去第一个总不会错
	    	int allSumMax = Integer.MIN_VALUE;
	    	// 行最大值
	    	int rowSumMax = 0;
	    	int rowSum = 0;
	    	/**
	    	 * 既然是子序列，那么[-i----------j--] i和j就是在 [0,len]之间,i < j
	    	 * i 从0开始，len-2结束。 len-1 即最后一个元素流给j
	    	 * j 从i开始，len-1结束
	    	 * 从编码看：如果
	    	 */
	    	for (int i = 0; i < len ; i++) {
	    		rowSum = nums[i];
	    		rowSumMax = nums[i];
	    		for (int j = i + 1; j < len; j++) {
	    			// 每次累计
	    			rowSum += nums[j];
	    			// 只有当前数值>0 才可能比原来积累的最大值大，当然也可以比原来的小，是中间添加了交大的负值
	    			if(nums[j] > 0 && rowSum > rowSumMax){
	    				rowSumMax = rowSum;
	    			}
	    		}
	    		// 判断[i]子序列集合求和最大值 跟 最大值 之间的关系
	    		if(rowSumMax > allSumMax){
	    			allSumMax = rowSumMax;
	    		}
	    	}
	    	return allSumMax;
	    }

方案2：对穷举中 求和的改进

 public int maxSubArray1(int[] nums) {
	    	if(nums == null || nums.length == 0){
	    		return 0;
	    	}
	    	int len = nums.length;
	    	if(len == 1){
	    		return nums[0];
	    	}
	    	int sum = Integer.MIN_VALUE;
	    	int tempSum = 0;
	    	/**
	    	 * 既然是子序列，那么[-i----------j--] i和j就是在 [0,len]之间,i < j
	    	 * i 从0开始，len-2结束。 len-1 即最后一个元素流给j
	    	 * j 从i开始，len-1结束
	    	 * 从编码看：如果
	    	 */
	    	for (int i = 0; i < len ; i++) {
	    		for (int j = i; j < len; j++) {
	    			// 求子序列之和 [i,j]
	    			for (int k = i; k <= j; k++) {
	    				tempSum += nums[k];
	    			}
	    			// 如果当前序列，比我原来的大，就记录值
	    			if(tempSum > sum){
	    				sum = tempSum;
	    			}
	    			tempSum = 0;
	    		}
	    	}
	    	
	    	return sum;
	    }

方案3：对其实最大值的改进

思路： 想从这之间找到规律，不就可以遍历一次了。 

问题：1. 编码很麻烦，需要处理特例很多。2. 如果最大值并没有参与运算，下列红框的max之间就没有关系了，也就从根子上没法做。

补充方案：存储 不包含 第一个元素，如果5作为的单个序列的，其他子序列之和最大值，因为后边的最大值跟这个一定有关系。

继续改进:
[i]子序列集合：从上面可以看出i每遍历一个值，j就从i到length-1，形成了一个子序列集合。咱们就陈i子序列集合
[i]子序列集合求和最大值：i子序列每个序列的求和后 比较出来的最大值
1. 假如当前num[i] > 0 ; [i]子序列集合求和最大值 = [i+1]子序列集合求和最大值 + num[i] 
2. 类似：num[i] = 0; [i]子序列集合求和最大值  = [i+1]子序列集合求和最大值
3. 同理：num[i] < 0; [i]子序列集合求和最大值 + num[i]  = [i+1]子序列集合求和最大值 
合并序列集合求和最大值：[i]子序列集合求和最大值  he [i+1]子序列集合求和最大值   合并为 [i,i+1]子序列集合求和最大值
1. 假如当前num[i] > 0 ; [i]子序列集合求和最大值 就是 [i,i+1]子序列集合求和最大值
2. 类似：num[i] = 0; [i]或者[i]子序列集合求和最大值 就是 [i,i+1]子序列集合求和最大值
3. 同理：num[i] < 0; [i+1]子序列集合求和最大值 就是 [i,i+1]子序列集合求和最大值
特例：
1. 全是负数
2. 收尾有包含0的元素，如：001100
3. 元素为0和负数
4. 如果最大值就是第一项，说明第一项就没有参与运算，[i] 和 [i+1]也就没关系了，也就不适用了。
    - 记录不包含 第一项的最大值,这条路走下去就沟里边了

复制一个不怎么完善的代码，可以放在力扣中去执行，把特例第四项补充上，个人不建议做，一个算法补丁这么多，只能说刚开始的建模就有问题。

class Solution {
	    public int maxSubArray(int[] nums) {
	    	if(nums == null || nums.length == 0){
				return 0;
			}
			int len = nums.length;
			if(len == 1){
				return nums[0];
			}
			// 非0开始数组区间
			int startIndex = 0;
			for (int j = 0; j < len; j++) {
				if(nums[j] != 0){
					startIndex = j;
					break;
				}
			}
			int endIndex = 0;
			for (int j = len - 1; j >= 0; j--) {
				if(nums[j] != 0){
					endIndex = j;
					break;
				}
			}
			// 全是0场景
			if(startIndex == len || endIndex == -1){
				return 0;
			}
			
			// 所有的和最大值，默认去第一个总不会错
			int allSumMax = Integer.MIN_VALUE;
			// 计算 [0]子序列集合求和最大值
			int rowSumMax = nums[startIndex];
			int rowSum = nums[startIndex];
			// 所有都是负值
			boolean allNegativeData = nums[startIndex] <= 0;
			int allNegativeMax = nums[startIndex] ;
			for (int j = startIndex + 1; j <= endIndex; j++) {
				// 每次累计
				rowSum += nums[j];
				// 只有当前数值>0 才可能比原来积累的最大值大，当然也可以比原来的小，是中间添加了交大的负值
				if(nums[j] >= 0 && rowSum > rowSumMax){
					rowSumMax = rowSum;
				}
				// 如果出现正数，就不在继续
				if(nums[j] > 0 && allNegativeData){
					allNegativeData = false;
				}
				// 求最大值
				if(nums[j] > allNegativeMax){
					allNegativeMax = nums[j]; 
				}
			}
			// 解决全负数情况
			if(allNegativeData){
				// 前面还有0
				if(startIndex > 0 || endIndex < len - 1){
					return 0;
				}
				return allNegativeMax;
			}
			allSumMax = rowSumMax;
			
			// 遍历处理 [i+1]子序列集合求和最大值
			for (int i = startIndex + 1; i <= endIndex ; i++) {
				rowSumMax -= nums[i - 1];
				
				if(rowSumMax > allSumMax){
					allSumMax = rowSumMax;
				}
			}
			return allSumMax;
	    }
	}

后面继续补充 最大子数组(序列)和的 其他实现方法