PHP 最大子数组和问题

 PHP 常用例子

Kadane 算法用于查找连续子数组的最大和。 Kadane的算法基于寻找所有正的连续子数组并找到连续子数组的最大和的思想。

在这个算法中，创建了一个名为max_sum的变量来存储直到当前迭代元素的正连续子数组的最大和，并创建一个名为 current_sum 的变量来存储以当前迭代元素结束的正子数组的和。在每次迭代中，current_sum 与 max_sum 进行比较，如果 max_sum 大于 max_sum，则更新它。

示例:

要理解 kadane 算法，我们考虑一个数组 Array = [-3, 1, -8, 12, 0, -3, 5, -9, 4] 并讨论查找所有正连续子数组的最大和所采取的每个步骤。

 max_sum = current_sum = 0

  步骤 1: i = 0, Array[0] =  -3
  current_sum = current_sum + (-3) = -3
  设置 current_sum = 0 因为 current_sum < 0

  步骤 2: i = 1, Array[0] =  1
  current_sum = current_sum + 1 = 1
  更新 max_sum = 1 因为 current_sum > max_sum

  步骤 3: i = 2, Array[0] =  -8
  current_sum = current_sum + (-8) = -7
  设置 current_sum = 0 因为 current_sum < 0

  步骤 4: i = 3, Array[0] =  12
  current_sum = current_sum + 12 = 12
  更新 max_sum = 12 因为 current_sum > max_sum

  步骤 5: i = 4, Array[0] =  0
  current_sum = current_sum + 0 = 12

  步骤 6: i = 5, Array[0] =  -3
  current_sum = current_sum + (-3) = 9

  步骤 7: i = 6, Array[0] =  5
  current_sum = current_sum + 5 = 14
  更新 max_sum = 14 因为 current_sum > max_sum

  步骤 8: i = 7, Array[0] =  -9
  current_sum = current_sum + (-9) = 5

  步骤 9: i = 8, Array[0] =  4
  current_sum = current_sum + 4 = 9 

因此，经过所有迭代后，max_sum的值为14。这个的起始索引点和结束索引点子数组分别为 3 和 6。

<?php
//kadane 算法的函数
function kadane($Array, $n) {
  $max_sum = 0;
  $current_sum = 0;
  for($i=0; $i<$n; $i++) {
    $current_sum = $current_sum + $Array[$i];
    
    if ($current_sum < 0)
      $current_sum = 0; 
    
    if($max_sum < $current_sum)
      $max_sum = $current_sum; 
  }
  return $max_sum;
}

//测试代码
$MyArray = array(-3, 1, -8, 12, 0, -3, 5, -9, 4);
$n = sizeof($MyArray);
echo "最大子数组是: ".kadane($MyArray, $n);
?> 

上面的代码将给出以下输出:

最大子数组是: 14 

要获取最大子数组的位置，变量 max_start 和 max_end 借助变量 current_start 和 current_end 进行维护。

<?php
//kadane算法的函数
function kadane($Array, $n) {
  $max_sum = 0;
  $current_sum = 0;

  $max_start = 0;
  $max_end = 0;
  $current_start = 0;
  $current_end = 0;

  for($i=0; $i<$n; $i++) {
    $current_sum = $current_sum + $Array[$i];
    $current_end = $i;

    if ($current_sum < 0) {
      $current_sum = 0;
      //从下一个元素开始一个新序列
      $current_start = $current_end + 1;
    }

    if($max_sum < $current_sum) {
      $max_sum = $current_sum;
      $max_start = $current_start;
      $max_end = $current_end;
    }
  }
  
  echo "最大子数组是: ".$max_sum."\n";
  echo "max_Sum 的起始索引: ".$max_start."\n";
  echo "max_Sum 的结束索引: ".$max_end."\n";
}

//测试代码
$MyArray = array(-3, 1, -8, 12, 0, -3, 5, -9, 4);
$n = sizeof($MyArray);
kadane($MyArray, $n);
?> 

上面的代码将给出输出如下:

最大子数组是: 14
max_Sum 的起始索引: 3
max_Sum 的结束索引: 6 

时间复杂度:

Kadane 算法的时间复杂度为 θ(N)。