Archive

Archive for June 15, 2021

Python: Kadane’s Algorithm


Learning : Python, Algorithm, Math
Subject: Implement the Kadane’s Algorithm

Definition: Kadane’s Algorithm is to search in a one Dimensional Array [integer positive and negative numbers] for a we will largest Sum of contiguous subarray.

[NOTE: To keep the code as simple as we can, We WILL NOT ADD any user input Varevecations. Assuming that our user will Enter the right inputs.]

Algorithm To find the largest subset sum, we apply coming step:
We will use two variables:
current_max: to hold the max sum of thesub-set
start_again: will be as a flag to re-set the current_max

Algorithm:
1. Start from Element in the array index = 1, save it as start_again. Set Current_max to Array Element in index = 0.

2. Do sumation of start_again with the next element index + 1.

3. If current_max < start_again then re-set current_manx = start_again

4. If start_again < 0 then re-set start_again = 0

5. Repeat from 2 to 4 until the end of the array.

6. If we reach end of the Array, then return the current_max

More from Kadane’s Algorithm:
The aim of Kadane’s Algorithm is to return the Maximum sum of sub-set. But in our code here we will return the following:
1. Maximum sum of largest subset
2. The start Index and the End Index of the subset.
3. printing out the subset.

We will have three options in our application, as following:
1. Kadane’s Algorithm – Fast Run.
2. Kadane’s Algorithm – Step By Step.
9. Exit.

As we are doing in our Algorithms coding, we will use a Main-Menu, and a Function to help the user to enter the Array.

Coding
We will start with def create_array(): and will return the Array that the user will enter. here is the code..

Ali radwani python project code Kadane Algorithm



Now, here is the code for the Main-Menu and the Main application body. In Main application body code, we will use the while True : loop and calling the main_menu() function then with if statement we will check on the user_selection

The Main-Menu
Ali radwani python project code Kadane Algorithm
Here is the Main Application body code..

Ali radwani python project code Kadane Algorithm



Last, we will write the Function to get the Kadane’s Sum in a Fast-Run, the details one will be a copy with mode print-out statement to show the steps .. [All code is in Download Page.]
As we mentioned, Our Kadane’s function will return three things, the Grates Sum of a sub-set, and to position of that sub-set as start index and end index. Here is the code ..

Ali radwani python project code Kadane Algorithm
Here is a Run-Time screen ..

Ali radwani python project code Kadane Algorithm



We done with another Algorithm, looking forwards to solve new one in coming days.

..:: Have Fun with Coding ::.. 🙂


To Download my Python code (.py) files Click-Here



ali radwani ahradwani.com python projects codeFollow me on Twitter..

By: Ali Radwani