首页 > 试题广场 >

完美的序列

[编程题]完美的序列

热度指数：2635 时间限制：C/C++ 2秒，其他语言4秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

小易定义一个数字序列是完美的，当且仅当对于任意 $2 \leq i \leq n$ ，都满足 $\sum_{1 \leq j < i}{A_{j}} \leq A_{i}$ ，即每个数字都要大于等于前面所有数字的和。
现在给定数字序列 $A_{i}$ ，小易想请你从中找出最长的一段连续子序列，满足它是完美的。

输入描述:

第一行数据组数。对于每组数据，第一行一个整数，接下来一行个整数表示序列。

输出描述:

对于每组数据，一行一个数字表示最长完美的连续子序列的长度。

示例1

输入

输出

3
3

算法知识视频讲解

Java

酷宝向前冲

双指针滑动窗口 AC

public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int m = sc.nextInt();
    while(m-- > 0) {
        int n = sc.nextInt();
        int[] nums = new int[n];
        for(int i = 0; i < n; i++) {
            nums[i] = sc.nextInt();
        }
        System.out.println(longestSub(nums));
    }
}

public static int longestSub(int[] nums) {
    int i = 0, j = 1, max = 0, sum = nums[0],n = nums.length;
    while(j < n) {
        if(nums[j] >= sum) {
            sum += nums[j];
            max = Math.max(max, j-i+1);
            j++;
        } else {
            sum -= nums[i];
            i++;
        }
    }
    return max;
}

编辑于 2020-08-07 14:52:51 回复(1)