這道題花了很多時間,主要博主比較菜,花了很多時間去看這個動態規劃,了解的不夠深入,花了點心思寫了出來這個程序.
動態規劃,就是避免重復的計算,把上一次計算的結果直接拿來用,比如這道題目,如果最大值是負的,那說明整個數組都是負數.如果不是,則輸入的第一個數是第一組的最大值,第二個數的判斷就是為正還是為負,根據第一個數的正負來判斷下一步操作,同樣,每輸入一個數都是如此判斷.
~~~
import java.util.Scanner;
/*
* 如果最大值為負數,說明里面所有數都是負數,因此只要找到最大的素數即可
* 簡單的動態規劃的運用,把上一次比較結果存儲下來,用于下一次比較
*/
public class Main {
public static void main(String[] args) {
Scanner input = new Scanner(System.in);
int num,sum = 0,max = 0,max_;
//max為最終的輸出結果.sum存儲比較的結果
//max_存儲全是負數情況的最大值
boolean flag = false;
num = input.nextInt();
int a[] = new int[num];
for (int i = 0; i < num; i++) {
a[i] = input.nextInt();
sum = sum+a[i];
if(a[i] > 0){//確定是否為全負的數組
flag = true;
}
if(sum < 0){//動態規劃
sum = 0;
}
if(sum > max){
max = sum;
}
}
if(!flag){
max_ = a[0];
for (int i = 0; i < a.length; i++) {
if(a[i] > max_){
max_ = a[i];
}
}
System.out.println(max_);
}else {
System.out.println(max);
}
}
}
~~~
