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≤Array Size≤1051 \le \text{Array Size} \le 10^5

  • −104≤Array Element≤104-10^4 \le \text{Array Element} \le 10^4

Expected Complexities

  • Time Complexity: O(n)\mathcal{O}(n)

  • Auxiliary Space: O(n)\mathcal{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]))