PHP Program - Maximum Subarray Problem


Advertisements

Kadane's algorithm is used to find the maximum sum of a contiguous subarray. Kadane's algorithm is based on the idea of looking for all positive contiguous subarray and find the maximum sum of a contiguous subarray.

In this algorithm, a variable called max_sum is created to store maximum sum of the positive contiguous subarray till current iterated element and a variable called current_sum is created to store sum of the positive subarray which ends at current iterated element. In each iteration, current_sum is compared with max_sum, to update max_sum if it is greater than max_sum.

Example:

To understand the kadane's algorithm, lets consider an array $$Array = [-3, 1, -8, 12, 0, -3, 5, -9, 4]$$ and discuss each step taken to find the maximum sum of all positive contiguous subarray.

Insertion Sort

  max_sum = current_sum = 0

  Step 1: i = 0, Array[0] =  -3
  current_sum = current_sum + (-3) = -3
  Set current_sum = 0 because current_sum < 0

  Step 2: i = 1, Array[0] =  1
  current_sum = current_sum + 1 = 1
  update max_sum = 1 because current_sum > max_sum

  Step 3: i = 2, Array[0] =  -8
  current_sum = current_sum + (-8) = -7
  Set current_sum = 0 because current_sum < 0

  Step 4: i = 3, Array[0] =  12
  current_sum = current_sum + 12 = 12
  update max_sum = 12 because current_sum > max_sum

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

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

  Step 7: i = 6, Array[0] =  5
  current_sum = current_sum + 5 = 14
  update max_sum = 14 because current_sum > max_sum

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

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

Hence, after all iterations, the value of max_sum is 14. The stating index point and end index point of this subarray are 3 and 6 respectively.

<?php
// function for kadane's algorithm
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;
}

//test kadane's algorithm code
  $MyArray = array(-3, 1, -8, 12, 0, -3, 5, -9, 4);
  $n = sizeof($MyArray);
  echo "Maximum SubArray is: ".kadane($MyArray, $n);
?>

Output

Maximum SubArray is: 14

To get the location of maximum subarray, variables max_start and max_end are maintained with the help of variables current_start and current_end.

<?php
// function for kadane's algorithm
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;
      //Start a new sequence from next element
      $current_start = $current_end + 1;
    }
    if($max_sum < $current_sum)
    {
      $max_sum = $current_sum;
      $max_start = $current_start;
      $max_end = $current_end;
    }
  }
  echo "Maximum SubArray is: ".$max_sum."\n";
  echo "Start index of max_Sum: ".$max_start."\n";
  echo "End index of max_Sum: ".$max_end."\n";
}

//test kadane's algorithm code
  $MyArray = array(-3, 1, -8, 12, 0, -3, 5, -9, 4);
  $n = sizeof($MyArray);
  kadane($MyArray, $n);
?>

Output

Maximum SubArray is: 14
Start index of max_Sum: 3
End index of max_Sum: 6

Time Complexity:

The time complexity of Kadane's algorithm is $$\mathcal{O}(N)$$.


Previous Page Next Page
Advertisements