Algorithms for Coding Interviews in Java/

...

/

Solution: Maximum Subarray Sum

Solution: Maximum Subarray Sum

This review discusses the solution of the maximum subarray sum challenge in detail.

We'll cover the following...

Solution # 1

A naive solution to this problem is:

  1. Find the sum of all possible contiguous subarrays.
  2. Find the maximum of those sums.
  3. Return the sum.

This approach can easily be implemented using two for loops like this:

Press + to interact
class MaxSubArray {
 public static int maxSumArr(int[] arr) {
  int n = arr.length;
  int max = 0;
  //traversing the array
  for (int i = 0; i < n; i++) {
   
   int sum = 0;
   //going through all the possible successive combinations
   for (int j = i; j < n; j++) {
    
    sum += arr[j];
    if (sum > max) {
     //updating max sum
     max = sum;
    }
   }
  }
  return max;
 }
 public static void main(String[] args) {
  int[] arr = {-2, -3, 4, -1, -2, 1, 5, -3};
  System.out.println("Subarray with maximum sum is: " + maxSumArr(arr));
 }
}

Explanation

  • The outer loop goes through each element one by one, picking the starting element (line 6).
  • The inner loop goes through all the possible successive combinations of iith elements, and calculates their sum (lines 10 & 12).
  • A maxmax variable is replaced if a greater sum is found at any point in the nested loop structure (lines 13 & 15).

Let’s discuss efficient and advanced solutions next!

Time complexity

As you might have guessed, this approach takes ...