Search⌘ K
AI Features
Home
Courses
Algorithms for Coding Interviews in Java

Solution: Maximum Subarray Sum

Explore multiple solutions for the maximum subarray sum problem. Understand the naive quadratic approach, delve into the divide and conquer method for O(n log n) performance, and master Kadane's algorithm which solves it in linear time. This lesson equips you to implement and analyze these key algorithms for coding interviews.

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:

Java
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
...