Maximum Subarray Sum

Difficulty - Medium

Companies - Bloomberg Linkedin Microsoft

---

Problem Statement

Given an array arr[] of size n. The task is to find the sum of the contiguous subarray with the largest sum.

Example

The Largest Sum Contiguous Array is [12,0,-3,5] -> 12+0–3+5 = 14

---

Solutions

1. Kadane’s Algorithm

C++ Solution

#include <iostream>
#include <vector>
using namespace std;

int main(){
    int n; cin >> n;
    vector<int> arr(n);
    for (int i=0; i<n; i++) cin >> arr[i];
    int sum = 0, ans = 0;
    for(int i=0; i<n; i++){
        sum = max(sum,sum+arr[i]);
        ans = max(sum,ans);
    }
    cout << ans;
}

Java Solution

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] arr= new int[n];
        for (int i = 0; i < n; i++) {
            v[i] = sc.nextInt();
        }
        int sum = 0, ans = 0;
        for (int i = 0; i < n; i++) {
            sum = Math.max(sum, sum + arr[i]);
            ans = Math.max(sum, ans);
        }
        System.out.println(ans);
        sc.close();
    }
}

Python

n = int(input())
arr = list(map(int, input().split()))
sum, ans = 0, 0

for i in range(n):
    sum = max(sum, sum + arr[i])
    ans = max(sum, ans)

print(ans)

The approach involves iterating over the array and keeping track of two variables: sum and ans. The sum variable represents the maximum subarray sum that includes the current element. The ans variable represents the overall maximum subarray sum seen so far.

At each iteration, we update the sum variable as the maximum between the current element and the sum of the current element and the previous sum value. We also update the ans variable as the maximum between the current sum value and the previous ansvalue.

After iterating over the entire array, the ans variable will hold the maximum subarray sum.

Analysis

Time Complexity : O(n)

The code iterates through the input array once in the for loop, so the time complexity is O(n), where n is the length of the input array.

Inside the for loop, the max() function compares two values and returns the larger one. This has constant time complexity and is not dependent on the size of the input array.

Therefore, the overall time complexity of the code is O(n).

Space Complexity : O(n)

The code creates a vector of size n to store the input array. Since the size of the vector is proportional to the length of the input array, the space complexity is O(n).

The sum and ans variables are simple integers and have constant space complexity.

Therefore, the overall space complexity of the code is O(n).

---

2. Divide and Conquer

C++ Solution

#include <iostream>
#include <vector>
#include <climits>
using namespace std;

// Find the maximum subarray sum that crosses the middle element
int maxCrossingSum(vector<int> arr, int l, int m, int h){
    int sum = 0, left_sum = INT_MIN, right_sum = INT_MIN;
    // Traverse the left side of the middle element
    for (int i = m; i >= l; i--){
        sum += arr[i];
        // Update the maximum left sum if the current sum is greater
        if (sum > left_sum)
            left_sum = sum;
    }
    sum = 0;
    // Traverse the right side of the middle element
    for (int i = m + 1; i <= h; i++){
        sum += arr[i];
        // Update the maximum right sum if the current sum is greater
        if (sum > right_sum)
            right_sum = sum;
    }
    // Return the sum of the maximum left and right sums
    return left_sum + right_sum;
}

// Find the maximum subarray sum of a given subarray of arr[l..h]
int maxSubarraySum(vector<int> arr, int l, int h){
    // Base case: if there's only one element in the subarray, return it
    if (l == h)
        return arr[l];
    // Divide the subarray into two halves and recursively find the maximum subarray sum
    int m = (l + h) / 2;
    int left_sum = maxSubarraySum(arr, l, m);
    int right_sum = maxSubarraySum(arr, m + 1, h);
    // Find the maximum subarray sum that crosses the middle element
    int cross_sum = maxCrossingSum(arr, l, m, h);
    // Return the maximum of the three sums
    return max(max(left_sum, right_sum), cross_sum);
}

int main(){
    int n;
    cin >> n;
    vector<int> arr(n);
    for (int i = 0; i < n; i++)
        cin >> arr[i];
    // Find the maximum subarray sum of the entire array
    int max_sum = maxSubarraySum(arr, 0, n - 1);
    cout << max_sum;
    return 0;
}

Java Solution

// import Scanner class to read input from user
import java.util.Scanner;

public class Main {
  // Find the maximum sum of a subarray that crosses the midpoint
  public static int maxCrossingSum(int[] arr, int l, int m, int h) {
      int sum = 0, left_sum = Integer.MIN_VALUE, right_sum = Integer.MIN_VALUE;

      // Find the maximum sum of the left subarray
      for (int i = m; i >= l; i--) {
          sum += arr[i];
          if (sum > left_sum)
              left_sum = sum;
      }

      sum = 0;

      // Find the maximum sum of the right subarray
      for (int i = m+1; i <= h; i++) {
          sum += arr[i];
          if (sum > right_sum)
              right_sum = sum;
      }

      // Return the sum of the left and right subarrays
      return left_sum + right_sum;
  }

  // Find the maximum sum of a subarray using divide and conquer
  public static int maxSubarraySum(int[] arr, int l, int h) {
      if (l == h)
          return arr[l];

      int m = (l + h) / 2;
      int left_sum = maxSubarraySum(arr, l, m);
      int right_sum = maxSubarraySum(arr, m+1, h);
      int cross_sum = maxCrossingSum(arr, l, m, h);

      // Return the maximum sum of the left, right, and crossing subarrays
      return Math.max(Math.max(left_sum, right_sum), cross_sum);
  }

  public static void main(String[] args) {
      Scanner sc = new Scanner(System.in);
      int n = sc.nextInt();
      int[] arr = new int[n];

      // Input the array elements
      for (int i = 0; i < n; i++)
        arr[i] = sc.nextInt();

      // Find the maximum sum of a subarray and print it
      int max_sum = maxSubarraySum(arr, 0, n-1);
      System.out.println(max_sum);

      sc.close();
  }
}

Python Solution

# Define a function to find the maximum subarray sum that crosses the midpoint
def maxCrossingSum(arr, l, m, h):
    # Initialize variables to hold the left and right sums
    left_sum = float('-inf')
    right_sum = float('-inf')
    sum_val = 0

    # Find the maximum sum of the left half of the array
    for i in range(m, l-1, -1):
        sum_val += arr[i]
        if sum_val > left_sum:
            left_sum = sum_val

    # Reset the sum_val variable to 0
    sum_val = 0

    # Find the maximum sum of the right half of the array
    for i in range(m+1, h+1):
        sum_val += arr[i]
        if sum_val > right_sum:
            right_sum = sum_val

    # Return the sum of the left and right sums
    return left_sum + right_sum

# Define a function to find the maximum subarray sum recursively
def maxSubarraySum(arr, l, h):
    # Base case: if there is only one element, return it
    if l == h:
        return arr[l]

    # Find the midpoint of the array
    m = (l + h) // 2

    # Recursively find the maximum sum of the left half of the array
    left_sum = maxSubarraySum(arr, l, m)

    # Recursively find the maximum sum of the right half of the array
    right_sum = maxSubarraySum(arr, m+1, h)

    # Find the maximum sum that crosses the midpoint
    cross_sum = maxCrossingSum(arr, l, m, h)

    # Return the maximum of the left, right, and cross sums
    return max(left_sum, right_sum, cross_sum)

# Get the length of the array and the array itself from the user
n = int(input())
arr = list(map(int, input().split()))

# Find the maximum subarray sum of the array using the maxSubarraySum function
max_sum = maxSubarraySum(arr, 0, n-1)

# Print the maximum subarray sum
print(max_sum)

The approach of the divide and conquer algorithm involves dividing the array into two halves and recursively finding the maximum subarray sum in the left half, the right half, and the subarray crossing the middle. The maximum of these three values is the maximum subarray sum of the given array.

The maxCrossingSum function is used to find the maximum subarray sum that crosses the middle of the array. This function iterates from the middle element to the left and right ends of the array, calculating the maximum sum on each side separately.

The maxSubarraySum function is the main function that implements the divide and conquer approach. It recursively calls itself on the left half and the right half of the array, and calculates the maximum subarray sum crossing the middle element using the maxCrossingSumfunction.

Analysis

Time Complexity : O(nlogn)

The function maxSubarraySum performs a divide and conquer approach, where it divides the input array in half recursively until there is only one element left. Each recursive call takes O(n) time to find the maximum subarray sum that crosses the midpoint using the maxCrossingSum function, and there are logn levels of recursion. Therefore, the total time complexity is O(nlogn).

Space Complexity : O(logn)

The recursive calls to the maxSubarraySum function create a call stack that has a maximum depth of logn (where n is the size of the input array). In addition, there are some constant space variables used in the algorithm, such as the indices and sums, which do not depend on the size of the input array. Therefore, the overall space complexity of the algorithm is O(logn) + O(1), which can be simplified to O(logn).

---

3. Dynamic Programming

C++ Solution

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    int n; cin >> n;
    vector<int> arr(n);
    for(int i=0; i<n; i++) cin >> arr[i];

    vector<int> dp(n, arr[0]); // Initialize dp table with first element

    for(int i=1; i<n; i++) {
        // Calculate maximum sum ending at the current element
        dp[i] = max(arr[i], dp[i-1] + arr[i]);
    }

    int max_sum = *max_element(dp.begin(), dp.end()); // Find the maximum sum in dp table

    cout << max_sum << endl;
    return 0;
}

Java Solution

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] arr = new int[n];
        for(int i=0; i<n; i++) arr[i] = sc.nextInt();

        int[] dp = new int[n];
        dp[0] = arr[0]; // Initialize dp table with first element

        for(int i=1; i<n; i++) {
            // Calculate maximum sum ending at the current element
            dp[i] = Math.max(arr[i], dp[i-1] + arr[i]);
        }

        int max_sum = Arrays.stream(dp).max().getAsInt(); // Find the maximum sum in dp table

        System.out.println(max_sum);
        sc.close();
    }
}

Python Solution

n = int(input())
arr = list(map(int, input().split()))

# Initialize the dynamic programming table with the first element
dp = [arr[0]]

# Loop through the array and fill up the dynamic programming table
for i in range(1, n):
    # Calculate the maximum sum ending at the current element
    max_sum_ending_here = max(arr[i], dp[i-1] + arr[i])
    # Append the maximum sum ending at the current element to the dynamic programming table
    dp.append(max_sum_ending_here)

# Find the maximum sum in the dynamic programming table
max_sum = max(dp)

print(max_sum)

In this code, we first read in the input array arr and its size n. We then initialize a dynamic programming table dp with the first element of the array. We then loop through the array from the second element to the last, and for each element, we calculate the maximum sum that ends at that element. We calculate this value by taking the maximum of the current element and the sum of the previous element and the current element. We then append this maximum sum to the dynamic programming table dp.

After the loop, the dynamic programming table dp contains the maximum sums ending at each element of the input array. We then find the maximum value in the table and output it as the solution to the problem.

Analysis

Time Complexity : O(n)

We need to create a dynamic programming table dp of size n to store the maximum sum ending at each element of the input array. Since each element of the dp table depends only on the previous element and the corresponding element of the input array, we can update the dp table in a single pass through the input array. Therefore, the time complexity of the dynamic programming solution is O(n).

Space Complexity : O(n)

We need to store the input array arr of size n and the dynamic programming table dp of size n in memory. This gives a space complexity of O(n). Any other constant-size variables used in the algorithm will not significantly increase the space complexity of the algorithm. Therefore, the space complexity of the dynamic programming solution is also O(n).

---