線性實現最大子序列和

要求時間復雜度為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);
    }
    
    
}