Find Subarray with Max Sum #

Problem #

Given an array. Find the subarray with the max sum containing at least one element.

Examples #

  • [2, 3, -8, 7, -1, 2, 3] ➜ [7, -1, 2, 3]

  • [-2, -4] ➜ [-2]

  • [5, 4, 1, 7, 8] ➜ [5, 4, 1, 7, 8]

Constraints #

  • 1 ≤ arr.size() ≤ 10⁵

  • -10⁴ ≤ arr[i] ≤ 10⁴

Expected Complexities #

  • Time Complexity: O(n)O(n)

  • Auxiliary Space: O(n)O(n)

Solution #

Python
Numeric = int | float


def find_max_sum_subarray(arr: list[Numeric]) -> list[Numeric]:
    current_sum: Numeric = arr[0]
    max_sum: Numeric = arr[0]

    current_start_index: int = 0
    max_sum_start_index: int = 0
    max_sum_end_index: int = 0

    for i in range(1, len(arr)):
        if current_sum < 0:
            current_sum = arr[i]
            current_start_index = i
        else:
            current_sum += arr[i]

        if current_sum > max_sum:
            max_sum = current_sum
            max_sum_start_index = current_start_index
            max_sum_end_index = i

    return arr[max_sum_start_index : max_sum_end_index + 1]


print(find_max_sum_subarray([2, 3, -8, 7, -1, 2, 3]))
print(find_max_sum_subarray([-2, -4]))
print(find_max_sum_subarray([5, 4, 1, 7, 8]))