计蒜客---最大子阵列

这道题花了很多时间,主要博主比较菜,花了很多时间去看这个动态规划,了解的不够深入,花了点心思写了出来这个程序.

动态规划,就是避免重复的计算,把上一次计算的结果直接拿来用,比如这道题目,如果最大值是负的,那说明整个数组都是负数.如果不是,则输入的第一个数是第一组的最大值,第二个数的判断就是为正还是为负,根据第一个数的正负来判断下一步操作,同样,每输入一个数都是如此判断.

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);
        }
    }
}