LeetCode最大连续子序列和的最大值

最近刷leetcode碰见了最大子序列和的最大值得问题，结合自己想对dp有点了解，于是自己写了几种方法，逐步优化算法，一直达到自己认为的最优解，如果代码有失误，或者大佬们有更好的思路，可以共同探讨。

1.利用三层循环来做（暴力破解）

package Solution;

public class test3 {
	//实现最大连续子数组的求和，时间复杂度为(o(n^3)),空间复杂度o(n)
	static int mi,mj;
	public static void maxSum(int[] arr) {
		int max=arr[0];
		for(int i=1;i<arr.length;i++) {
			for(int j=i;j<arr.length;j++) {
				int sum=0;
				for(int k=i;k<=j;k++) {
					sum+=arr[k-1];
				}
				if(sum>max) {
					max=sum;
					mi=i-1;
					mj=j-1;
				}
			}
		}
		System.out.println("最大连续数组的和为:"+max);
	}
	public static void main(String[] args) {
		int[] arr= {3,-2,5,8,-4,-1,4};
		maxSum(arr);
		System.out.println("起始下标为:"+mi+" "+"终止下标为:"+mj);
	}
}

2.利用两层循环+一个数组来解决

package Solution;

public class test4 {
	static int mi,mj;
	//实现最大连续子数组的求和，时间复杂度为(o(n^2)+o(n)),空间复杂度o(2n)
	public static void maxSum(int[] arr,int[] sun) {
		for(int i=1;i<sun.length;i++) {
			sun[i]=sun[i-1]+arr[i-1];
		}
		int max=sun[0];
		for(int i=1;i<sun.length;i++) {
			for(int j=i;j<sun.length;j++) {
				int num=sun[j]-sun[i-1];
				if(num>max) {
					max=num;
					mi=i-1;
					mj=j-1;
				}	
			}
		}
		System.out.println("最大连续子数组的和:"+max);
	}
	public static void main(String[] args) {
		int[] arr= {3,-2,-5,8,-4,-1,4,9,-1};
		int[] sun=new int[arr.length+1];
		maxSum(arr,sun);
		System.out.println("起始下标为:"+mi+" "+"终止下标为:"+mj);
	}
}

3.利用分治思想解决

package Solution;
/**
 * 用分治实现最大连续子序列求和
 * @author quanhangbo
 *
 */
public class test5 {
	static int maxL,maxR;
	//此处的x，y表示的是左开右闭的区间
	public static int maxSum(int[] arr,int x,int y) {
		 int mid=(x+y)/2;
		 if(y-x==1)return arr[x];
		 //递归着求解左边的最大值
		 maxL=maxSum(arr,x,mid);
		 //递归着求解右边的最大值
		 maxR=maxSum(arr,mid,y);
		 //求解跨区域的左半部分的最大值
		 int maxLeftSum,leftSum;
		 maxLeftSum=leftSum=0;
		 for(int i=mid-1;i>=0;i--) {
			 leftSum+=arr[i];
			 if(leftSum>maxLeftSum) {
				 maxLeftSum=leftSum;
			 }
		 }
		 //求解跨区域的右半部分的最大值
		 int maxRightSum,rightSum;
		 maxRightSum=rightSum=0;
		 for(int i=mid;i<arr.length;i++) {
			 rightSum+=arr[i];
			 if(rightSum>maxRightSum) {
				 maxRightSum=rightSum;
			 }
		 }
		 //比较左边的最大值，和右边的最大值和跨区域的最大值
		 return Math.max(Math.max(maxL,maxR),maxLeftSum+maxRightSum);
	}
	public static void main(String[] args) {
		int[] arr= {3,-2,-5,8,-4,-1,4,9,-1};
		
		System.out.println(maxSum(arr,0,arr.length));
	}
}

4.利用动态规划解决

package Solution;

import java.util.Arrays;
/**
 * 最大连续子序列求和
 * @author quanhangbo
 *
 */
public class test11 {
	public static void main(String[] args) {
		int[] arr=new int[] {-2,-1};
		int i,x=arr[0];
		//遍历数组，其中arr[i]表示的是连续子数组中当前的最大和值（只有两个选择，要么加，要么不加，比较这两种情况求最大值）
		for(i=1;i<arr.length;i++) {
			arr[i]=Math.max(arr[i],arr[i-1]+arr[i]);//遍历完后arr数组中的最大值，就是最大连续子序列的和
			x=Math.max(x,arr[i]);//这里的作用就是求数组中的最大值
		}
		System.out.println(x);
	}
}

5.递推解决(至今感觉最优的解法了)时间复杂度o（n）,空间复杂度o(1)

package Solution;

public class test12 {
	public static void main(String[] args) {
		int[] arr=new int[] {-2,1,-3,4,-1,2,1,-5,4};
		int arrsum=arr[0],sum=0;
		for(int i=0;i<arr.length;i++) {
			sum+=arr[i];
			if(sum>arrsum) {
				arrsum=sum;
			}
			if(sum<0) {
				sum=0;
			}
		}
		System.out.println(arrsum);
	}

}

这是最后一个代码在leetcode中的运行结果。