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≤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(1)\mathcal{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]))