Kadane's Algorithm Maximum Subarray in DSA Python - Build from Scratch

Kadane's Algorithm Maximum Subarray

📖 Scenario: You are analyzing daily temperature changes to find the longest warm streak. The temperature changes are recorded as a list of numbers, where positive numbers mean warmer days and negative numbers mean colder days.

🎯 Goal: Build a program that uses Kadane's Algorithm to find the maximum sum of a continuous subarray in the list of temperature changes. This helps identify the longest warm streak.

📋 What You'll Learn

Create a list called temp_changes with the exact values: [2, -1, 3, -4, 5, -2, 6, -1]

Create a variable called max_sum and set it to the first element of temp_changes

Create a variable called current_sum and set it to 0

Use a for loop with variable change to iterate over temp_changes

Inside the loop, update current_sum by adding change

If current_sum is less than change, set current_sum to change

If current_sum is greater than max_sum, set max_sum to current_sum

Print the value of max_sum

💡 Why This Matters

🌍 Real World

Finding the longest warm streak or best period in temperature changes helps meteorologists and farmers plan better.

💼 Career

Kadane's Algorithm is a classic technique used in software engineering interviews and real-world problems involving maximum sums in sequences.

1

Create the list of temperature changes

Create a list called temp_changes with these exact values: [2, -1, 3, -4, 5, -2, 6, -1]

DSA Python

# Create the list temp_changes with the given values
# Your code here

Hint

Use square brackets to create a list and separate numbers with commas.

2

Set up variables for Kadane's Algorithm

Create a variable called max_sum and set it to the first element of temp_changes. Then create a variable called current_sum and set it to 0.

DSA Python

temp_changes = [2, -1, 3, -4, 5, -2, 6, -1]
# Create max_sum and current_sum variables
# Your code here

Hint

Use temp_changes[0] to get the first element of the list.

3

Implement Kadane's Algorithm loop

Use a for loop with variable change to iterate over temp_changes. Inside the loop, add change to current_sum. If current_sum is less than change, set current_sum to change. If current_sum is greater than max_sum, set max_sum to current_sum.

DSA Python

temp_changes = [2, -1, 3, -4, 5, -2, 6, -1]
max_sum = temp_changes[0]
current_sum = 0
# Write the for loop and update current_sum and max_sum
# Your code here

Hint

Remember to update current_sum first, then compare and update it if needed. Finally, update max_sum if current_sum is bigger.

4

Print the maximum subarray sum

Print the value of max_sum.

DSA Python

temp_changes = [2, -1, 3, -4, 5, -2, 6, -1]
max_sum = temp_changes[0]
current_sum = 0
for change in temp_changes:
    current_sum += change
    if current_sum  max_sum:
        max_sum = current_sum
# Print max_sum
# Your code here

Hint

Use print(max_sum) to show the result.