Print Subarray with Maximum Sum using Kadane’s Algorithm - Optimal Approach

Given an array of integers (which may include positive numbers, negative numbers, and zeros), your task is to find and print the subarray that has the maximum sum.

If multiple subarrays have the same maximum sum, return the one that appears first. If the array is empty, return an empty result or appropriate message.

Understanding the Problem

We are given an array of integers that may include positive numbers, negative numbers, or zeros. Our goal is to find the contiguous subarray that has the highest possible sum. This is commonly known as the "Maximum Subarray" problem.

In simple terms, a subarray is a continuous portion of the original array. We are not allowed to skip elements. We need to return both the maximum sum and the subarray that gives this sum.

Let’s consider an example:

Input: [-2, 1, -3, 4, -1, 2, 1, -5, 4]

We want to find the subarray with the maximum sum. In this case, the correct answer is:

Subarray: [4, -1, 2, 1]  
Maximum Sum: 6

Step-by-Step Approach

To solve this problem, we use a modified version of Kadane's Algorithm. Here's how we will go step-by-step:

1. Initialize: We start with variables to track the maximum sum so far, the current sum while traversing, and the indices of the start and end of the best subarray.
2. Traverse: For each element:
   • Add it to the current sum.
   • If the current sum is greater than the maximum so far, update the maximum and store the current subarray boundaries.
   • If the current sum becomes negative, reset it to 0 and mark the next index as a potential start of the next subarray.
3. Return: At the end of the loop, return the subarray between the best start and end indices, and the maximum sum.

Edge Cases and How We Handle Them

• All Positive Elements: The sum increases as we include more elements. The whole array is the answer.
• All Negative Elements: Since adding any two elements will decrease the sum, we pick the single element with the least negative value.
• Mixed Elements: This is the typical use case. Kadane's algorithm handles it by resetting the sum when needed and updating the subarray bounds.
• Empty Array: No elements mean no subarray. We return a sum of 0 and an empty subarray.
• All Zeros: Although all values are the same (0), we still pick a single element. Usually, the first zero is returned with a sum of 0.

Explanation

Imagine you’re walking through the array with a basket. You keep adding numbers to your basket. If the total weight (sum) becomes negative, you drop everything and start a new basket. But every time your basket has the best total so far, you note down the items inside it. By the end, you’ll have the best basket you picked up along the way — the one with the highest total.

Final Result

With the help of this step-by-step strategy and edge case handling, we can always return the correct maximum subarray and its sum, even in tricky cases like all negatives or empty arrays.

1. Given an array arr of integers (positive, negative, or zero).
2. Initialize max_sum = arr[0], current_sum = arr[0], start = 0, end = 0, and temp_start = 0.
3. Iterate through the array from index 1:
4. → If current_sum + arr[i] is less than arr[i], set current_sum = arr[i] and temp_start = i.
5. → Else, add arr[i] to current_sum.
6. → If current_sum > max_sum, update max_sum = current_sum, start = temp_start, end = i.
7. After loop, the subarray from start to end gives the maximum sum.

O(1)

Explanation: The algorithm uses only a fixed number of variables (like max_sum, current_sum, start, end, temp_start) and no additional data structures, hence constant space.