求一个环内连续m个数的最大和

云计算 waitig 469℃ 百度已收录 0评论

题目描述:

有n个小朋友,围成一个圈,玩丢手绢的游戏。现输入一个数组表示每个小朋友被丢中的次数,同时输入一个整数m(1<=m<=n),求出连续m个小朋友被丢中次数的和的最大值。
示例:

input:
5//数组大小n
1
2
3
4
5//数组的个元素值
3//连续m个小朋友
output:
12

思路:

思路还是比较简单的:
假定输入数组为arr,连续m个小朋友
1. 求出一个基本值sum,max
for i between 0:(m-1) in arr
    sum += arr[i];
max = sum;
2. len = arr.length.
sum1:表示从当前位置i开始,连续m个数值的和
sum1 = arr[i]+arr[i+1]+...+arr[i+m-1];
那么,从下一个位置i+1开始,连续m个数值的和sum2,
sum2 = arr[i+1]+arr[i+1]+...+arr[i+m];
sum2 = sum1 - arr[i] + arr[i+m];

为了避免每次迭代i都去判断if(i >= len),然后再取模,这里的循环直到i = len - m为止,即叠加的最后一个元素为arr[len - 1].这就都不用判断if(i >= len)。
for i between m:(len - m) in arr
    sum -= arr[i-1];
    sum += arr[m];
    if(sum > max)
        max = sum;
3. j = 0, for i between (len - m + 1): (len -1) in arr
    sum -= arr[i - 1];
    sum += arr[j++];
    if(sum > max)
        max = sum;

根据上述分析,写出代码如下:

import java.util.Scanner;

/**
 * @author Mengjun Li
 * @create 2017/10/14
 * @since 1.0.0
 */
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int i = 0;
        int[] num = new int[n];
        while (i < n) {
            num[i++] = sc.nextInt();
        }
        int m = sc.nextInt();
        System.out.println(solve(num, m));
    }

    public static int solve(int[] num, int m) {
        if (num == null)
            return 0;
        int len = num.length;
        if (len == 0)
            return 0;
        int sum = 0, max = 0;
        for (int i = 0; i < m; i++)
            sum += num[i];
        max = sum;
        for (int i = 1; i <= len - m; i++) {
            sum -= num[i - 1];
            sum += num[i + m-1];
            if (max < sum)
                max = sum;
        }
        for (int i = len - m + 1, j = 0; i < len; i++, j++) {
            sum = sum - num[i - 1] + num[j];
            if (max < sum)
                max = sum;
        }
        return max;
    }
}

输入输出:
input:

5
1
2
3
4
5
3

output:

12

本文由【waitig】发表在等英博客
本文固定链接:求一个环内连续m个数的最大和
欢迎关注本站官方公众号,每日都有干货分享!
等英博客官方公众号
点赞 (0)分享 (0)