迅雷笔试题

inknk

seufy88

回复 76# iamlimeng


    我是这样想的,找两个位置start,end
0到start的总和为负的,同时end到数组结尾总和也是负的,那么start,end之间就是所求的东西了.

my @arr=(9, -12, 120, 8, -20, 100, 30, -89, 20);

my $start;
my $end;

foreach my $i (0..$#arr){
        if( sum_forward($i) <0){
        foreach my $j ($i..$#arr){
                if( sum_afterward($j) <0){
                        $start=$i;
                        $end=$j;
                        }else{
                        next;
                        }
                }
        }else{
        next;
        }
}

my $res=join "\t",(@arr)[$start..$end];
print $res;


sub sum_forward{
        my $pos=shift;
        my $sum=0;
        foreach my $i (0..($pos-1)){
        $sum+=$arr[$i];
        }
        return $sum;
        }

sub sum_afterward{
        my $pos=shift;
        my $sum=0;
        foreach my $i (($pos+1)..$#arr){
        $sum+=$arr[$i];
        }
        return $sum;
        }

btdm123

如果在考场上遇到这种题目，用最naive的方法实现，如Thompson常说，when in doubt, use brute force,只有当规模很大时，复杂算法才有意义

btdm123

用动态规划来考虑是这样的：
对数组A［0..n］,问题规模为n,假设解为其片段A[i,j]是它的解，当问题规模扩展到n+1时，即求A[0..n+1]的解，可以证明，这个解只可能是A[i,j]和A[i,n+1]两者之一。时间复杂度是O(n)

ljmmail

[img]

[/img]