小算法

手写无明显bug算法

• 给定一个数组序列, 需要求选出一个区间, 使得该区间是所有区间中经过如下计算的值最大的一个：

区间中的最小数 × 区间所有数的和最后程序输出经过计算后的最大值即可，不需要输出具体的区间。如给定序列  [6 2 1]则根据上述公式, 可得到所有可以选定各个区间的计算值:
[6] = 6 * 6 = 36;

[2] = 2 * 2 = 4;

[1] = 1 * 1 = 1;

[6,2] = 2 * 8 = 16;

[2,1] = 1 * 3 = 3;

[6, 2, 1] = 1 * 9 = 9;

输入例子1:

3
6 2 1

输出例子1:

36

思路描述：
首先解必然存在，假设解以分别以每一个元素为最小元素来向前后扩展该序列，对拿到的n个序列求max

$n = 3;
$a = [6, 2, 1];

function max_min_sum($a)
{
    $max = 0;
    foreach ($a as $i => $aa) {
        $tmp = subb($a, $i);
        if($tmp > $max) $max = $tmp;
    }
    return $max;
}

function subb($a, $min_index)
{
    $l = $r = $min_index;
    $len = count($a);
    $sum = $a[$min_index];
    while($l-1 >= 0 && $a[$l-1] >= $a[$min_index]){
        $l--;
        $sum += $a[$l];
    }
    while($r+1 < $len && $a[$r+1] >= $a[$min_index]){
        $r++;
        $sum += $a[$r];
    }
    // return [$l, $r];
    return $a[$min_index]*$sum;
}

echo max_min_sum($a);

本作品采用《CC 协议》，转载必须注明作者和本文链接