计蒜客—最大子阵列
最后更新于：2022-04-01 09:41:09
这道题花了很多时间,主要博主比较菜,花了很多时间去看这个动态规划,了解的不够深入,花了点心思写了出来这个程序.
动态规划,就是避免重复的计算,把上一次计算的结果直接拿来用,比如这道题目,如果最大值是负的,那说明整个数组都是负数.如果不是,则输入的第一个数是第一组的最大值,第二个数的判断就是为正还是为负,根据第一个数的正负来判断下一步操作,同样,每输入一个数都是如此判断.
~~~
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);
}
}
}
~~~