Algorithms

Algorithms

Kadane's Algorithm

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.

Implementation of Kadane's Algorithm

# function for kadane's algorithm
def kadane(MyList):
  max_sum = 0
  current_sum = 0
  for i in MyList: 
    current_sum = current_sum + i
    if current_sum < 0:
      current_sum = 0
    if max_sum < current_sum:
      max_sum = current_sum
  return max_sum
  
# test the code                 
MyList = [-3, 1, -8, 12, 0, -3, 5, -9, 4]
print("Maximum SubArray is:",kadane(MyList))

The above code will give the following output:

Maximum SubArray is: 14

public class MyClass {
  // function for kadane's algorithm
  static int kadane(int Array[]) {
    int max_sum = 0;
    int current_sum = 0;
    int n = Array.length;

    for(int 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 the code
  public static void main(String[] args) {
    int[] MyArray = {-3, 1, -8, 12, 0, -3, 5, -9, 4};
    System.out.println("Maximum SubArray is: " + kadane(MyArray));
  }
}

The above code will give the following output:

Maximum SubArray is: 14

#include <iostream>
using namespace std;

// function for kadane's algorithm
static int kadane(int Array[], int n) {
  int max_sum = 0;
  int current_sum = 0;
  for(int 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 the code
int main() {
  int MyArray[] = {-3, 1, -8, 12, 0, -3, 5, -9, 4};
  int n = sizeof(MyArray) / sizeof(MyArray[0]);
  cout<<"Maximum SubArray is: "<<kadane(MyArray, n);
  return 0;
}

The above code will give the following output:

Maximum SubArray is: 14

#include <stdio.h>

// function for kadane's algorithm
static int kadane(int Array[], int n) {
  int max_sum = 0;
  int current_sum = 0;
  for(int 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 the code
int main() {
  int MyArray[] = {-3, 1, -8, 12, 0, -3, 5, -9, 4};
  int n = sizeof(MyArray) / sizeof(MyArray[0]);
  printf("Maximum SubArray is: %i", kadane(MyArray, n));
  return 0;
}

The above code will give the following output:

Maximum SubArray is: 14

using System;

class MyProgram {
  // function for kadane's algorithm
  static int kadane(int[] Array) {
    int max_sum = 0;
    int current_sum = 0;
    int n = Array.Length;
    for(int 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 the code
  static void Main(string[] args) {
    int[] MyArray = {-3, 1, -8, 12, 0, -3, 5, -9, 4};
    Console.Write("Maximum SubArray is: " + kadane(MyArray));
  }
}

The above code will give the following output:

Maximum SubArray is: 14

<?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 the code
$MyArray = array(-3, 1, -8, 12, 0, -3, 5, -9, 4);
$n = sizeof($MyArray);
echo "Maximum SubArray is: ".kadane($MyArray, $n);
?>

The above code will give the following 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.

# function for kadane's algorithm
def kadane(MyList):
  max_sum = 0
  current_sum = 0

  max_start = 0
  max_end = 0
  current_start = 0
  current_end = 0

  for i in range(len(MyList)): 
    current_sum = current_sum + MyList[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
      
  print("Maximum SubArray is:", max_sum)
  print("Start index of max_Sum:", max_start)
  print("End index of max_Sum:", max_end)
  
# test the code                 
MyList = [-3, 1, -8, 12, 0, -3, 5, -9, 4]
kadane(MyList)

The above code will give the following output:

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

public class MyClass {
  // function for kadane's algorithm
  static void kadane(int Array[]) {
    int max_sum = 0;
    int current_sum = 0;
    int n = Array.length;

    int max_start = 0;
    int max_end = 0;
    int current_start = 0;
    int current_end = 0;

    for(int 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;
      }
    }

    System.out.println("Maximum SubArray is: " + max_sum);
    System.out.println("Start index of max_Sum: " + max_start);
    System.out.println("End index of max_Sum: " + max_end);
  }

  // test the code
  public static void main(String[] args) {
    int[] MyArray = {-3, 1, -8, 12, 0, -3, 5, -9, 4};
    kadane(MyArray);
  }
}

The above code will give the following output:

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

#include <iostream>
using namespace std;

// function for kadane's algorithm
static void kadane(int Array[], int n) {
  int max_sum = 0;
  int current_sum = 0;

  int max_start = 0;
  int max_end = 0;
  int current_start = 0;
  int current_end = 0;

  for(int 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;
    }
  }

  cout<<"Maximum SubArray is: "<<max_sum<<"\n";
  cout<<"Start index of max_Sum: "<<max_start<<"\n";
  cout<<"End index of max_Sum: "<<max_end<<"\n";
}

// test the code
int main() {
  int MyArray[] = {-3, 1, -8, 12, 0, -3, 5, -9, 4};
  int n = sizeof(MyArray) / sizeof(MyArray[0]);
  kadane(MyArray, n);
  return 0;
}

The above code will give the following output:

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

#include <stdio.h>

// function for kadane's algorithm
static void kadane(int Array[], int n) {
  int max_sum = 0;
  int current_sum = 0;

  int max_start = 0;
  int max_end = 0;
  int current_start = 0;
  int current_end = 0;

  for(int 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;
    }
  }

  printf("Maximum SubArray is: %i\n", max_sum);
  printf("Start index of max_Sum: %i\n", max_start);
  printf("End index of max_Sum: %i\n", max_end);
}

// test the code
int main() {
  int MyArray[] = {-3, 1, -8, 12, 0, -3, 5, -9, 4};
  int n = sizeof(MyArray) / sizeof(MyArray[0]);
  kadane(MyArray, n);
  return 0;
}

The above code will give the following output:

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

using System;

class MyProgram {
  // function for kadane's algorithm
  static void kadane(int[] Array) {
    int max_sum = 0;
    int current_sum = 0;
    
    int max_start = 0;
    int max_end = 0;
    int current_start = 0;
    int current_end = 0;

    int n = Array.Length;
    for(int 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;
      }
    }

    Console.WriteLine("Maximum SubArray is: " + max_sum);
    Console.WriteLine("Start index of max_Sum: " + max_start);
    Console.WriteLine("End index of max_Sum: " + max_end);
  }

  // test the code
  static void Main(string[] args) {
    int[] MyArray = {-3, 1, -8, 12, 0, -3, 5, -9, 4};
    kadane(MyArray);
  }
}

The above code will give the following output:

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

<?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 the code
$MyArray = array(-3, 1, -8, 12, 0, -3, 5, -9, 4);
$n = sizeof($MyArray);
kadane($MyArray, $n);
?>

The above code will give the following 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 Θ(N).

AlphaCodingSkills

AlphaCodingSkills Android App

AlphaCodingSkills is a online learning portal that provides tutorials on Python, Java, C++, C, C#, PHP, R, Ruby, Rust, Scala, Swift, Perl, SQL, Data Structures and Algorithms. Tutorials, examples, references and content of the website are reviewed and simplified continuously to improve comprehensibility and eliminate any possible error. We use cookies to ensure best browsing experience on our website. While using this website, you acknowledge to have read and accepted our cookie and privacy policy.