Print Subarray with Maximum Sum - Extension of Kadane's Algorithm

Algorithm Steps

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

Find and Print Subarray with Maximum Sum using Kadane's Algorithm Code

Python

JavaScript

Java

C++

def max_subarray_with_indices(arr):
    max_sum = current_sum = arr[0]
    start = end = temp_start = 0

    for i in range(1, len(arr)):
        if arr[i] > current_sum + arr[i]:
            current_sum = arr[i]
            temp_start = i
        else:
            current_sum += arr[i]

        if current_sum > max_sum:
            max_sum = current_sum
            start = temp_start
            end = i

    print("Maximum Sum:", max_sum)
    print("Subarray:", arr[start:end+1])

# Sample Input
arr = [-2, 1, -3, 4, -1, 2, 1, -5, 4]
max_subarray_with_indices(arr)