2251: 蓝桥杯算法提高-数组求和

解题思路:

注意事项:

参考代码:

import java.util.ArrayList;
import java.util.Scanner;

public class 数组求和 {

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		/*
		 * 题目 2251: [蓝桥杯][算法提高]数组求和 时间限制: 1Sec 内存限制: 128MB 提交: 218 解决: 123 题目描述
		 * 输入n个数，围成一圈，求连续m（m<n）个数的和最大为多少？ 输入 输入的第一行包含两个整数n, m。第二行，共n个整数。
		 * 
		 * 0<m<n<1000, -32768<=输入的每个数<=32767。
		 * 
		 * 输出 输出1行，包含一个整数，连续m个数之和的最大值。 样例输入 10 3 9 10 1 5 9 3 2 6 7 4 样例输出 23
		 */
		Scanner scanner = new Scanner(System.in);
		int n = scanner.nextInt();
		int m = scanner.nextInt();
		ArrayList<Integer> arrayList = new ArrayList<Integer>();
		int max = 0;
		int number = 0;
		int head = 0;
		for (int i = 0; i < n; i++) {
			int sum = scanner.nextInt();
			if (i > m - 1) {
				int last = number;// 之前连续三数的和
				number = number - arrayList.get(head) + sum;
				max = Math.max(max, number > last ? number : last);
				head++;// 出队
			} else {
				number += sum;
				max += sum;
			}
			arrayList.add(sum);
		}
		//注意是一个圈 所以 最后一个可以和第一个 第二个相加（假设连续三个数）
		int zuiho = 0;
		while (head != n) {
			int last = number;// 之前连续三数的和
			number = number - arrayList.get(head) + arrayList.get(zuiho);
			max = Math.max(max, number > last ? number : last);
			zuiho++;
			head++;// 出队
		}

		System.out.println(max);
	}

}