线性实现最大子序列和

要求时间复杂度为O（n），实现最大子序列的和，并找到最大序列的起始位置和终止位置。例如输入的数组为1, -2, 3, 10, -4, 7, 2, -5，最大子序列为3, 10, -4, 7, 2，因此输出为该子数组的和18，开始位置为2，终止位置为6。dp[i]=max{num[i],dp[i-1]}，其中dp[i]表示以i为末尾节点的最大子序列和，具体看接下来的代码，我这边已经写的很详细了。如果大家都什么好的优化或者有什么没考虑到的还请大家积极指出。package TestProject;import java.util.Scanner;/** * 最大子序列的和，时间复杂度为O（n），可以查询出最大子序列的开始位置、截止位置、值 * @author xuhui * */public class MaxSubArray {public static void main（String[] args）{Scanner scanner = new Scanner（System.in）;int len = scanner.nextInt（）;//输入序列的长度int[] num = new int[len];//初始化数组int[] dp = new int[len];for（int i=0;i<len;i++）{num[i] = scanner.nextInt（）;dp[i] = num[i];}int begin = 0;//记录最大序列开始位置int s = 0;//记录序列子序列的起始位置int end = 0;//记录最大序列结束的位置int max_sum = dp[0];//最大序列的和for（int i=1;i<len;i++）{//更新以i为末尾节点的最大最序列值dp[i]=max{num[i],dp[i-1]+num[i]}if（dp[i]<=（dp[i-1]+num[i]））{dp[i]=dp[i-1]+num[i];}else{//保证末尾节点为i最大子序列的起始位置s=i;}if（dp[i]>max_sum）{max_sum = dp[i];end = i;begin = s;}}System.out.print（"begin:"+begin+" end:"+end+" max_sum:"+max_sum）;}}本文永久更新链接地址：http://www.linuxidc.com/Linux/2016-07/133652.htm