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

Kadane's Algorithm Maximum Subarray

📖 Scenario: You are analyzing daily temperature changes to find the longest period of warming. You want to find the maximum sum of consecutive temperature changes in a list.

🎯 Goal: Build a program that uses Kadane's Algorithm to find the maximum sum of a contiguous subarray in an integer array.

📋 What You'll Learn

Create an integer array with exact values

Create an integer variable to hold the array size

Implement Kadane's Algorithm using a for loop

Print the maximum subarray sum

💡 Why This Matters

🌍 Real World

Kadane's Algorithm is used in finance to find the best time to buy and sell stocks for maximum profit, or in signal processing to find the strongest signal segment.

💼 Career

Understanding Kadane's Algorithm helps in solving array and dynamic programming problems efficiently, a common requirement in software engineering interviews and real-world coding tasks.

1

Create the integer array

Create an integer array called arr with these exact values: -2, 1, -3, 4, -1, 2, 1, -5, 4.

DSA C

# Your code here

Hint

Use curly braces to list the array values exactly as given.

2

Set the array size

Create an integer variable called n and set it to the size of arr (which is 9).

DSA C

int arr[] = {-2, 1, -3, 4, -1, 2, 1, -5, 4};
# Your code here

Hint

Count the number of elements in arr and assign it to n.

3

Implement Kadane's Algorithm

Create two integer variables max_so_far and max_ending_here, both initialized to arr[0]. Then use a for loop with variable i from 1 to n - 1 to update max_ending_here as the maximum of arr[i] and max_ending_here + arr[i], and update max_so_far as the maximum of max_so_far and max_ending_here.

DSA C

int arr[] = {-2, 1, -3, 4, -1, 2, 1, -5, 4};
int n = 9;
// Your code here

Hint

Use a for loop starting from 1 to n-1. Update max_ending_here and max_so_far inside the loop.

4

Print the maximum subarray sum

Use printf to print the value of max_so_far followed by a newline.

DSA C

int arr[] = {-2, 1, -3, 4, -1, 2, 1, -5, 4};
int n = 9;
int max_so_far = arr[0];
int max_ending_here = arr[0];
for (int i = 1; i  arr[i]) {
        max_ending_here = max_ending_here + arr[i];
    } else {
        max_ending_here = arr[i];
    }
    if (max_so_far < max_ending_here) {
        max_so_far = max_ending_here;
    }
}
// Your code here

Hint

Use printf("%d\n", max_so_far); to print the result.