求数组有最大值时的子数组 php

1个回答

  • 程序如下:

    //和最大的连续子数组计算

    $arr=array(1,2,3,4,-1,5,6,-9,6,1);

    $max_sum='';//最大和

    $max_i='';//最大和子数组开始下标

    $max_j='';//最大和的子数组结束下标

    $n=count($arr)-1;//数组最大下标

    for ($i=0;$i<=$n;$i++){

    $sum=0;

    for ($j=$i;$j<=$n;$j++){

    $sum+=$arr[$j];

    //此时sum值为$i...$j子数组之和

    if ($max_sum==='' || $sum>$max_sum){

    $max_sum=$sum;

    $max_i=$i;

    $max_j=$j;

    }

    }

    }

    //输出结果

    echo "和最大的连续连续子数组和为 $max_sum";

    echo "是从 $max_i .... $max_j 的子数组";

    echo "内容是:";

    for ($i=$max_i;$i<=$max_j;$i++) echo $arr[$i],", "

    ?>程序运行结果为:和最大的连续连续子数组和为 20

    是从 0 .... 6 的子数组

    内容是:1, 2, 3, 4, -1, 5, 6, 如果$arr=array(-5,1,2,3,4,-1,5,6,-9,6,1),那么运行的结果为:和最大的连续连续子数组和为 20

    是从 1 .... 7 的子数组

    内容是:1, 2, 3, 4, -1, 5, 6,