Kadane’s Algorithm

Given an integer array arr[]. Find the contiguous sub-array(containing at least one number) that has the maximum sum and return its sum.

Examples:

Input: arr[] = [1, 2, 3, -2, 5]
Output: 9
Explanation: Max subarray sum is 9 of elements (1, 2, 3, -2, 5) which is a contiguous subarray.

Input: arr[] = [-1, -2, -3, -4]
Output: -1
Explanation: Max subarray sum is -1 of element (-1)

Input: arr[] = [5, 4, 7]
Output: 16
Explanation: Max subarray sum is 16 of element (5, 4, 7)

Expected Time Complexity: O(n)
Expected Auxiliary Space: O(1)

Constraints:
1 ≤ arr.size() ≤ 10⁵
-10⁷ ≤ arr[i] ≤ 10⁷

Approach 01:

#include <vector>
#include <algorithm> // For std::max

class Solution {
public:
    long maxSubarraySum(const std::vector<int>& numbers) {
        long currentSum = 0;
        long maxSum = LONG_MIN; // Initialized to the smallest possible value

        for (int number : numbers) {
            currentSum += number;
            maxSum = std::max(maxSum, currentSum);

            if (currentSum < 0) {
                currentSum = 0; // Reset the current sum if it becomes negative
            }
        }
        return maxSum;
    }
};

class Solution:
    def maxSubArraySum(self, numbers):
        currentSum = 0
        maxSum = float('-inf') # Initialized to the smallest possible value

        for number in numbers:
            currentSum += number
            maxSum = max(maxSum, currentSum)

            if currentSum < 0:
                currentSum = 0 # Reset the current sum if it becomes negative
        
        return maxSum

Time Complexity

• Iteration over the Array:

  The function iterates over the input vector numbers exactly once. During this iteration, it performs constant-time operations for each element. Thus, the time complexity is \( O(n) \), where n is the number of elements in the input vector.

• Overall Time Complexity:

  The overall time complexity of the function is \( O(n) \).

Space Complexity

• Auxiliary Space:

  The function uses a constant amount of extra space for variables currentSum and maxSum. Therefore, the auxiliary space complexity is \( O(1) \).

• Input Space:

  The input vector numbers is passed by reference, so no additional space is required for the input.

• Overall Space Complexity:

  The overall space complexity is \( O(1) \).