給定K個整數組成的序列{ N1, N2, ..., NK },“連續子列”被定義為{ Ni, Ni+1, ..., Nj },其中 1。“最大子列和”則被定義為所有連續子列元素的和中最大者。例如給定序列{ -2, 11, -4, 13, -5, -2 },其連續子列{ 11, -4, 13 }有最大的和20。現要求你編寫程式,計算給定整數序列的最大子列和。
本題旨在測試各種不同的算法在各種資料情況下的表現。各組測試資料特點如下:
- 資料1:與樣例等價,測試基本正确性;
- 資料2:102個随機整數;
- 資料3:103個随機整數;
- 資料4:104個随機整數;
- 資料5:105個随機整數;
輸入格式:
輸入第1行給出正整數K (≤);第2行給出K個整數,其間以空格分隔。
輸出格式:
在一行中輸出最大子列和。如果序列中所有整數皆為負數,則輸出0。
輸入樣例:
6
-2 11 -4 13 -5 -2
輸出樣例:
20
問題解決「線上處理」,意思是指沒輸入一個資料就進行技術處理,在任何一個地方終止輸入,算法都能給出正确的值,展現在方法中的for循壞裡面。
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
// TODO Auto-generated method stub
Scanner sc = new Scanner(System.in);
int t = sc.nextInt();
int[] a = new int[t];
for(int i = 0;i < t;i++) {
a[i] = sc.nextInt();
}
System.out.println(max(t,a));
}
public static int max(int n,int[] a) {
int thisHalf = 0, maxHalf = 0;
for(int j = 0;j < n;j++) {
thisHalf += a[j];
if(thisHalf > maxHalf) {
maxHalf = thisHalf;
}
else if(thisHalf < 0) {
thisHalf = 0;
}
}
return maxHalf;
}
}
送出結果: