你的位置:首页 > Java教程

[Java教程]线性实现最大子序列和


要求时间复杂度为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);  }    }