Finding the Largest Sum of a Subarray

Problem

Given an integer array arr[], find the maximum sum of a subarray (containing at least one element).
A subarray is a continuous part of the array.

Example 1
Input: arr = [2, 3, -8, 7, -1, 2, 3]
Output: 11
Explanation: Subarray [7, -1, 2, 3] gives the maximum sum 11.

Example 2
Input: arr = [-2, -4]
Output: -2
Explanation: Subarray [-2] has the maximum sum.

Approach (Kadane’s Algorithm)

Start with the first element as the current and maximum sum.
Traverse the array from the second element.
At each step:
Either start a new subarray from the current element.
Or extend the existing subarray.
Update the maximum sum if a larger sum is found.

Python Code

class Solution:
def maxSubarraySum(self, arr):
max_sum = arr[0]
curr_sum = 0

    for num in arr:
        curr_sum += num

        if curr_sum > max_sum:
            max_sum = curr_sum

        if curr_sum < 0:
            curr_sum = 0

    return max_sum

Output
11
-2
25