线性实现最大子序列和

线性实现最大子序列和

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

本文永久更新链接地址：