Question

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

例如，有$arr=array(1,2,3,4,-1,5,6,-9,6,1),求拥有最大值时的子数组，这里我们知道子数组是(1,2,3,4,-1,5,6）。要求子数组是连续的前N项，而不是只取正数。
当$arr=array(1,2,3,4,-1,5,6,-9,6,1,…),求程序

Answer 1

程序如下：

<?php
  //和最大的连续子数组计算
  $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\n";
  echo "是从 $max_i .... $max_j 的子数组\n";
  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,