Skip to main content

Kadane's Algorithm | The-Algorithm-Drive | MyCodingNetwork

Kadane's Algorithm

Kadane’s algorithm is used to find largest contagious subarray sum for a given array. It is one of the most common types of algorithms used to find the subarray with largest sum. The time complexity of this algorithm is O(N).


    Output:  

     

Code Explanation:

On line 4, there’s an int array variable a[ ], which is the array on which we have to perform our task. We have stored the value of the array, in variable l.

cur_max, is a temporary variable for traversing the array and storing positive sum occurring and update it after each iteration. global_max, is a variable for storing the highest sum of subarray. ‘start’ variable stores the starting index of the desired subarray and ‘end’ variable stores the last index of that subarray, that is, contagious subarray with the highest sum.

Working:

Talking about the working of this algorithm, it uses one for loop and the entire operation can be performed in just one traversal of the array. One of the limitations of this algorithm is that it needs at least one positive number in the array otherwise it will not work.


Algorithm:

1.   Start

2.   Declare an array with at least one positive number.

3.   Declare two counter variables, first, cur_max for current sum and the other global_max for global sum. The variable global_max will be initialized with minimum integer value. The variable global_max will store largest sum of the required subarray.

4.   Declare a for loop starting from the first index and terminating at the last index. Inside the for loop,

cur_max += a[i]

if(cur_max>global_max)

{

global_max=cur_max

}

if (cur_max<0)

{

cur_max=0

}

End of for loop

 

Variable cur_max is used to add the elements of the array at each iteration and compare it with the value of global_max at each iteration. If the value of global_max is less than cur_max then assign it with the value of cur_max. If the value of cur_max is less than 0 then assign cur_max with the value 0.

5.   The value stored in the global_max variable is the output of our program.

   

Hope you liked this explanation, for any doubt or feedback you can comment down in the comment section.

Labels:

Popular posts from this blog

Pattern 6 | Java | MyCodingNetwork | Alok Tripathi (Code 8)

Problem Statement: Write a program to make a square and mark out its diagonals. Accept the length as input from the user and give output in the following manner: And ( In simple words, we have printed stars (*) on the boundary positions of the matrix and on the centre positions of the matrix we have printed blank space( ) )   THE CODE: Sample Output: In the above program, two int variables r to accept the length of square as input. On line 7, following statement is used to accept the input from the user: int r = sc . nextInt ();   For taking the input Scanner class has been used, more about Scanner class Algorithm: Two for loops are defined: ·         First for loop with counter variable i has initial value 1, conditional statement i less than or equal to r and an updating statement i++ . ·         Inside the first loop there is a second for loop, with counter variable j has ini...
Discover More »

YouTube Material 1| Hindi Video

Video Lecture- https://youtu.be/StCjnwfS0NQ Basic structure of a Java program public class xyz { public static void main(String args[]) { //Code //Code //Code //Code //Code }} public - access specifier/modifiers which makes the particular entity accessible throughout the program i.e., it can be accessed by other classes also. static - a keyword by which we don't have to create an object of that particular entity. void- return type keyword by which the function becomes non-returning type. main - name of the function String args[] - argument for main function Print Statement Syntax: System.out.println() ; Three types of Iteration statements are: for loop Example: for(int i=0; i<=5;i++) { //Code //Code //Code //Code //Code } The body of the above for loop will be executed 6 times. while loop( entry control loop) Syntax: while (condition) { //Code //Code //Code //Code //Code } The body of the above while loop will be executed continuously as long as the condition of the while is tr...
Discover More »

Pattern 1 | Java

Problem Statement: Write a program to draw the following pattern of NxN(where N is the input): * * * * * * * * * * * * * * * * * * * * * * * * * (here, N=5) THE CODE Output: Here, the input is 8 Simplification : In the above problem, two for loops are used: 1. The first for loop is having i as counter variable with  initial value of 1 and ending value of 10 with an updation statement i++. 2. The second for loop is having j as counter variable with initial value of 1 and ending value of 10 with an updation statement j++. The second  for loop is used to print  * in the respective column (the value of j represents the column number). It is having a print statement System.out.println("* ") to print * in each column(for convenience, I've added a space for better visibility of columns in the output). The first for loop is used to define rows( the value of i represents the row number). It is having a print statement System.out.print() to change rows each time the second for ...
Discover More »