Find Max Sum of Subarray #

Problem #

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

Examples #

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

    • The subarray [7, -1, 2, 3] has the largest sum.

  • [-2, -4] ➜ -2

    • The subarray [-2] has the largest sum.

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

    • The subarray [5, 4, 1, 7, 8] has the largest sum.

Constraints #

  • 1 ≤ arr.size() ≤ 10⁵

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

Expected Complexities #

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

  • Auxiliary Space: O(1)O(1)

Solution #

Python
Numeric = int | float


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

    for i in range(1, len(arr)):
        current_sum = max(current_sum + arr[i], arr[i])
        max_sum = max(max_sum, current_sum)

    return max_sum


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