問題：給定一整數(shù)序列A1，

A2，... An (可能有負(fù)數(shù))，求A1~An的一個(gè)子序列Ai~Aj，使得Ai到Aj的和最大

例如：整數(shù)序列-2, 11, -4, 13, -5, 2, -5, -3, 12, -9的最大子序列的和為21。

從左到右記錄當(dāng)前子序列的和sum，開始位置為start，結(jié)束位置為end。若sum不斷增加，那么最大子序列的和max也不斷增加(不斷更新max，start，end)。如果往前掃描中遇到負(fù)數(shù)，那么當(dāng)前子序列的和將會減小。此時(shí)sum

將會小于max，當(dāng)然max也就不更新。如果sum降到0時(shí)，說明前面已經(jīng)掃描的那一段就可以拋棄了，這時(shí)將sum置為0，并且start為下一個(gè)位置。然后，sum將從后面開始將這個(gè)子段進(jìn)行分析，若有比當(dāng)前max大的子段，繼續(xù)更新max。這樣一趟掃描結(jié)果也就出來了。

為了檢驗(yàn)代碼，通過浙大PAT的題目來測試http://pat.zju.edu.cn/contests/pat-a-practise/1007

import java.util.Scanner;

public class Main {

public static void main(String[] args) {

int k,i;

int[] arr=new int[10008];

Scanner sc=new Scanner(System.in);

boolean negativeAll=true;

k=sc.nextInt();

for(i=0;i

arr[i]=sc.nextInt();

if(arr[i]>=0){

negativeAll=false;

}

}

if(negativeAll){

System.out.println(0+" "+arr[0]+" "+arr[k-1]);

}

else{

int sum=0,stmp=0,start=0,end=0,imax=-1;

for(i=0;i

sum=sum+arr[i];

if(sum>imax){

start=stmp;

end=i;

imax=sum;

}

if(sum<0){

sum=0;

stmp=i+1;

}

}

System.out.println(imax+" "+arr[start]+" "+arr[end]);

}

}

}

總結(jié)

以上是生活随笔為你收集整理的java实现最长连续子序列_Java实现O(n)最大连续子序列和 | 学步园的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。