7-1 最大子列和问题 (20 分)

落日映苍穹つ 2022-02-04 02:59 159阅读 0赞

7-1 最大子列和问题 (20 分)  
给定K个整数组成的序列\{ N  
1  
 , N  
2  
 , …, N  
K  
 \}，“连续子列”被定义为\{ N  
i  
 , N  
i+1  
 , …, N  
j  
 \}，其中 1≤i≤j≤K。“最大子列和”则被定义为所有连续子列元素的和中最大者。例如给定序列\{ -2, 11, -4, 13, -5, -2 \}，其连续子列\{ 11, -4, 13 \}有最大的和20。现要求你编写程序，计算给定整数序列的最大子列和。

本题旨在测试各种不同的算法在各种数据情况下的表现。各组测试数据特点如下：

数据1：与样例等价，测试基本正确性；  
数据2：102个随机整数；  
数据3：103个随机整数；  
数据4：104个随机整数；  
数据5：105个随机整数；  
输入格式:  
输入第1行给出正整数K (≤100000)；第2行给出K个整数，其间以空格分隔。

输出格式:  
在一行中输出最大子列和。如果序列中所有整数皆为负数，则输出0。

输入样例:  
6  
\-2 11 -4 13 -5 -2  
输出样例:  
20

import java.util.Scanner;
    
    public class Main {
    
    	public static void main(String[] args) {
    		// TODO Auto-generated method stub
    		Scanner scanner = new Scanner(System.in);
    		int N = scanner.nextInt();
    		int[] a = new int[N];
    		int[] b = new int[N + 1];
    		boolean flag = false;
    		for (int i = 0; i < N; i++) {
    			a[i] = scanner.nextInt();
    			if (a[i]>0) {
    				flag = true;
    			}
    			b[i] = a[i];
    		}
    		b[0] = a[0];
    
    		for (int i = 1; i < N; i++) {
    			//最大上升序列和，不连续
    			/*
    			 * for (int j = 0; j < i; j++) { if (a[i] > a[j]) {
    			 * 
    			 * if (b[j] + a[i] > b[i]) { b[i] = b[j] + a[i]; } } }
    			 */
    			//最大上升子序列和，连续
    			/*
    			 * if (a[i] > a[i - 1]) { if (b[i-1]+a[i]>=b[i]) { b[i]=b[i-1]+a[i]; } }
    			 */
    
    			if (b[i - 1] + a[i] >= b[i]) {
    				b[i] = b[i - 1] + a[i];
    			}
    
    			//System.out.printf("i:%d %d\n", i, b[i]);
    		}
    		int max_value = b[0];
    		for (int i = 1; i < N; i++) {
    			if (b[i] > max_value) {
    				max_value = b[i];
    			}
    		}
    		if (flag) {
    			System.out.println(max_value);
    		}else {
    			System.out.println(0);
    		}
    		
    	}
    }