给定一个数组V,我们需要找到两个索引(i,j),使得V [j]> V [i]和(j - i)最大

Question

给定阵列V,我们需要找到两个索引(i,j),使得V [j]> V [i]和(j-i)是最大的.

蛮力方法非常简单,其中对于索引i处的每个值(范围从1到n),我们比较索引j处的值(范围从i + 1到n).到目前为止,我们跟踪最大值(ji)以找到最终答案.

该方法具有O(n ^ 2)的时间复杂度.有没有人提出改善时间复杂度的建议？

Answer 1

复杂度为 O(N) 的算法：

#!/usr/bin/perl

use strict;
use warnings;

sub dump_list { print join(", ", map sprintf("%2d", $_), @_), "\n" }

for (0..20) {
    # generate a random list of integers with some convenient bias:
    my @l = (map int(rand(20) + 20 - $_), 0..19);

    my $max = $l[-1];
    my $min = $l[0];

    my @max;
    for my $l (reverse @l) {
        $max = $l if $l > $max;
        push @max, $max;
    }
    @max = reverse @max;

    my @min;
    for my $l (@l) {
        $min = $l if $l < $min;
        push @min, $min;
    }

    my $best_i = 0;
    my $best_j = -1;
    my $best   = -1;

    my $j = 0;
    for my $i (0..$#l) {
        while ($j < @l) {
            last unless $max[$j] > $min[$i];
            $j++;
            if ($j - $i > $best) {
                $best = $j - 1 - $i;
                $best_i = $i;
                $best_j = $j - 1;
            }
        }
    }

    print "list: "; dump_list @l;
    print "idxs: "; dump_list 0..$#l;
    print "best: $best, i: $best_i, j: $best_j\n\n";
}

更新：响应 Nohsib 请求：

假设您有一个随机数字列表（a[0]、a[1]、a[2]、a[3]...、a[N-1]）

第一步是为每个数字找到左侧的最大值 masmax[i] = maximum(a[0], a[1], ..., a[i])和右侧的最小值min[i] = minimum(a[i], a[i+1], ..., a[N-1])。

a[j] < a[k]一旦你有了这些数组，找到最大化的区间k-j就几乎是微不足道的了。

尝试在纸上做一些随机列表，你会很容易找出背后的逻辑。