求数组的所有子数组的和的最大值
发布网友
发布时间：2022-06-01 16:17
共1个回答
热心网友
时间：2023-10-08 14:23
<?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,
