Maximum Subarray

Definition

Definition

The Maximum Subarray Algorithm is a method used to find the contiguous subarray within a one-dimensional array of numbers which has the largest sum

Explanation

Iterate through the array, keeping track of the current sum of the subarray and the maximum sum found so far. It updates these values as it traverses the array, ensuring that the current sum is either extended by the next element or reset to the next element itself, whichever is greater. At each step, it also compares the current sum with the maximum sum found so far and updates the maximum sum accordingly. By the end of the iteration, the algorithm returns the maximum sum found and the corresponding subarray

Guidance

• Initialize variables: max_sum = current_sum = array[0]
• Iterate through the array starting from the second element
• For each element
  • Update current_sum to be the maximum of the current element or the sum of the current element and the previous current_sum
  • Update max_sum to be the maximum of max_sum and current_sum
• After iterating through the array, return max_sum

Tips

• utilize Kadane's Algorithm for an optimized solution
• focus on keeping track of the maximum sum and the current sum efficiently to minimize space complexity

Practice

Practice

maxSubarray(array):
  max_sum = current_sum = array[0]  // Initialize variables
  for i from 1 to length(array)-1:   // Iterate through the array
    current_sum = max(array[i], current_sum + array[i]) // Update current sum
    max_sum = max(max_sum, current_sum)  // Update max sum
  return max_sum  // Return the maximum sum found

Solution

package main

import (
	"math"
)

func BfMaximumSubarray(inputArray []int) []int {
	maxSubarrayStartIndex := 0
	maxSubarrayLength := 0
	var maxSubarraySum *int

	for startIndex := 0; startIndex < len(inputArray); startIndex++ {
		subarraySum := 0
		for arrLength := 1; arrLength <= len(inputArray)-startIndex; arrLength++ {
			subarraySum += inputArray[startIndex+(arrLength-1)]
			if maxSubarraySum == nil || subarraySum > *maxSubarraySum {
				maxSubarraySum = &subarraySum
				maxSubarrayStartIndex = startIndex
				maxSubarrayLength = arrLength
			}
		}
	}

	return inputArray[maxSubarrayStartIndex : maxSubarrayStartIndex+maxSubarrayLength]
}

func DcMaximumSubarraySum(inputArray []int) int {
	var solveRecursively func(int, bool) int
	solveRecursively = func(elementIndex int, mustPick bool) int {
		if elementIndex >= len(inputArray) {
			if mustPick {
				return 0
			}
			return math.MinInt32
		}
		return int(math.Max(
			float64(inputArray[elementIndex]+solveRecursively(elementIndex+1, true)),
			float64(solveRecursively(elementIndex+1, false)),
		))
	}

	return solveRecursively(0, false)
}

func DpMaximumSubarray(inputArray []int) []int {
	maxSum := math.Inf(-1)
	currentSum := 0.0

	maxStartIndex := 0
	maxEndIndex := len(inputArray) - 1
	currentStartIndex := 0

	for currentIndex, currentNumber := range inputArray {
		currentSum += float64(currentNumber)

		if maxSum < currentSum {
			maxSum = currentSum
			maxStartIndex = currentStartIndex
			maxEndIndex = currentIndex
		}

		if currentSum < 0 {
			currentSum = 0
			currentStartIndex = currentIndex + 1
		}
	}

	return inputArray[maxStartIndex : maxEndIndex+1]
}

import java.util.Arrays;

public class MaximumSubarray {

  public static int[] bfMaximumSubarray(int[] inputArray) {
    int maxSubarrayStartIndex = 0;
    int maxSubarrayLength = 0;
    int maxSubarraySum = Integer.MIN_VALUE;

    for (int startIndex = 0; startIndex < inputArray.length; startIndex++) {
      int subarraySum = 0;
      for (int arrLength = 1; arrLength <= inputArray.length - startIndex; arrLength++) {
        subarraySum += inputArray[startIndex + (arrLength - 1)];
        if (maxSubarraySum == Integer.MIN_VALUE || subarraySum > maxSubarraySum) {
          maxSubarraySum = subarraySum;
          maxSubarrayStartIndex = startIndex;
          maxSubarrayLength = arrLength;
        }
      }
    }

    return Arrays.copyOfRange(inputArray, maxSubarrayStartIndex, maxSubarrayStartIndex + maxSubarrayLength);
  }

  public static int dcMaximumSubarraySum(int[] inputArray) {
    return solveRecursively(inputArray, 0, false);
  }

  private static int solveRecursively(int[] inputArray, int elementIndex, boolean mustPick) {
    if (elementIndex >= inputArray.length) {
      return mustPick ? 0 : Integer.MIN_VALUE;
    }
    return Math.max(
        inputArray[elementIndex] + solveRecursively(inputArray, elementIndex + 1, true),
        mustPick ? 0 : solveRecursively(inputArray, elementIndex + 1, false)
    );
  }

  public static int[] dpMaximumSubarray(int[] inputArray) {
    int maxSum = Integer.MIN_VALUE;
    int currentSum = 0;

    int maxStartIndex = 0;
    int maxEndIndex = inputArray.length - 1;
    int currentStartIndex = 0;

    for (int currentIndex = 0; currentIndex < inputArray.length; currentIndex++) {
      currentSum += inputArray[currentIndex];

      if (maxSum < currentSum) {
        maxSum = currentSum;
        maxStartIndex = currentStartIndex;
        maxEndIndex = currentIndex;
      }

      if (currentSum < 0) {
        currentSum = 0;
        currentStartIndex = currentIndex + 1;
      }
    }

    return Arrays.copyOfRange(inputArray, maxStartIndex, maxEndIndex + 1);
  }
}

function bfMaximumSubarray(inputArray) {
  let maxSubarrayStartIndex = 0;
  let maxSubarrayLength = 0;
  let maxSubarraySum = null;

  for (let startIndex = 0; startIndex < inputArray.length; startIndex += 1) {
    let subarraySum = 0;
    for (
      let arrLength = 1;
      arrLength <= inputArray.length - startIndex;
      arrLength += 1
    ) {
      subarraySum += inputArray[startIndex + (arrLength - 1)];
      if (maxSubarraySum === null || subarraySum > maxSubarraySum) {
        maxSubarraySum = subarraySum;
        maxSubarrayStartIndex = startIndex;
        maxSubarrayLength = arrLength;
      }
    }
  }

  return inputArray.slice(
    maxSubarrayStartIndex,
    maxSubarrayStartIndex + maxSubarrayLength,
  );
}

function dcMaximumSubarraySum(inputArray) {
  function solveRecursively(elementIndex, mustPick) {
    if (elementIndex >= inputArray.length) {
      return mustPick ? 0 : -Infinity;
    }
    return Math.max(
      inputArray[elementIndex] + solveRecursively(elementIndex + 1, true),
      mustPick ? 0 : solveRecursively(elementIndex + 1, false),
    );
  }

  return solveRecursively(0, false);
}

function dpMaximumSubarray(inputArray) {
  let maxSum = -Infinity;
  let currentSum = 0;

  let maxStartIndex = 0;
  let maxEndIndex = inputArray.length - 1;
  let currentStartIndex = 0;

  inputArray.forEach((currentNumber, currentIndex) => {
    currentSum += currentNumber;

    if (maxSum < currentSum) {
      maxSum = currentSum;
      maxStartIndex = currentStartIndex;
      maxEndIndex = currentIndex;
    }

    if (currentSum < 0) {
      currentSum = 0;
      currentStartIndex = currentIndex + 1;
    }
  });

  return inputArray.slice(maxStartIndex, maxEndIndex + 1);
}

fun bfMaximumSubarray(inputArray: IntArray): IntArray {
    var maxSubarrayStartIndex = 0
    var maxSubarrayLength = 0
    var maxSubarraySum: Int? = null

    for (startIndex in inputArray.indices) {
        var subarraySum = 0
        for (arrLength in 1..inputArray.size - startIndex) {
            subarraySum += inputArray[startIndex + (arrLength - 1)]
            if (maxSubarraySum == null || subarraySum > maxSubarraySum!!) {
                maxSubarraySum = subarraySum
                maxSubarrayStartIndex = startIndex
                maxSubarrayLength = arrLength
            }
        }
    }

    return inputArray.sliceArray(maxSubarrayStartIndex until maxSubarrayStartIndex + maxSubarrayLength)
}

fun dcMaximumSubarraySum(inputArray: IntArray): Int {
    fun solveRecursively(elementIndex: Int, mustPick: Boolean): Int {
        if (elementIndex >= inputArray.size) {
            return if (mustPick) 0 else Int.MIN_VALUE
        }
        return Math.max(
                inputArray[elementIndex] + solveRecursively(elementIndex + 1, true),
                if (mustPick) 0 else solveRecursively(elementIndex + 1, false)
        )
    }

    return solveRecursively(0, false)
}

fun dpMaximumSubarray(inputArray: IntArray): IntArray {
    var maxSum = Int.MIN_VALUE
    var currentSum = 0

    var maxStartIndex = 0
    var maxEndIndex = inputArray.size - 1
    var currentStartIndex = 0

    inputArray.forEachIndexed { currentIndex, currentNumber ->
        currentSum += currentNumber

        if (maxSum < currentSum) {
            maxSum = currentSum
            maxStartIndex = currentStartIndex
            maxEndIndex = currentIndex
        }

        if (currentSum < 0) {
            currentSum = 0
            currentStartIndex = currentIndex + 1
        }
    }

    return inputArray.sliceArray(maxStartIndex..maxEndIndex)
}

def bfMaximumSubarray(inputArray):
    maxSubarrayStartIndex = 0
    maxSubarrayLength = 0
    maxSubarraySum = None

    for startIndex in range(len(inputArray)):
        subarraySum = 0
        for arrLength in range(1, len(inputArray) - startIndex + 1):
            subarraySum += inputArray[startIndex + (arrLength - 1)]
            if maxSubarraySum is None or subarraySum > maxSubarraySum:
                maxSubarraySum = subarraySum
                maxSubarrayStartIndex = startIndex
                maxSubarrayLength = arrLength

    return inputArray[maxSubarrayStartIndex:maxSubarrayStartIndex + maxSubarrayLength]

def dcMaximumSubarraySum(inputArray):
    def solveRecursively(elementIndex, mustPick):
        if elementIndex >= len(inputArray):
            return 0 if mustPick else float('-inf')
        return max(
            inputArray[elementIndex] + solveRecursively(elementIndex + 1, True),
            0 if mustPick else solveRecursively(elementIndex + 1, False)
        )

    return solveRecursively(0, False)

def dpMaximumSubarray(inputArray):
    maxSum = float('-inf')
    currentSum = 0

    maxStartIndex = 0
    maxEndIndex = len(inputArray) - 1
    currentStartIndex = 0

    for currentIndex, currentNumber in enumerate(inputArray):
        currentSum += currentNumber

        if maxSum < currentSum:
            maxSum = currentSum
            maxStartIndex = currentStartIndex
            maxEndIndex = currentIndex

        if currentSum < 0:
            currentSum = 0
            currentStartIndex = currentIndex + 1

    return inputArray[maxStartIndex:maxEndIndex + 1]

fn bf_maximum_subarray(input_array: &[i32]) -> Vec<i32> {
    let mut max_subarray_start_index = 0;
    let mut max_subarray_length = 0;
    let mut max_subarray_sum: Option<i32> = None;

    for start_index in 0..input_array.len() {
        let mut subarray_sum = 0;
        for arr_length in 1..=input_array.len() - start_index {
            subarray_sum += input_array[start_index + (arr_length - 1)];
            if max_subarray_sum.is_none() || subarray_sum > max_subarray_sum.unwrap() {
                max_subarray_sum = Some(subarray_sum);
                max_subarray_start_index = start_index;
                max_subarray_length = arr_length;
            }
        }
    }

    input_array[max_subarray_start_index..max_subarray_start_index + max_subarray_length].to_vec()
}

fn dc_maximum_subarray_sum(input_array: &[i32]) -> i32 {
    fn solve_recursively(input_array: &[i32], element_index: usize, must_pick: bool) -> i32 {
        if element_index >= input_array.len() {
            if must_pick {
                0
            } else {
                i32::MIN
            }
        } else {
            i32::max(
                input_array[element_index] + solve_recursively(input_array, element_index + 1, true),
                if must_pick {
                    0
                } else {
                    solve_recursively(input_array, element_index + 1, false)
                },
            )
        }
    }

    solve_recursively(input_array, 0, false)
}

fn dp_maximum_subarray(input_array: &[i32]) -> Vec<i32> {
    let mut max_sum = i32::MIN;
    let mut current_sum = 0;

    let mut max_start_index = 0;
    let mut max_end_index = input_array.len() - 1;
    let mut current_start_index = 0;

    for (current_index, &current_number) in input_array.iter().enumerate() {
        current_sum += current_number;

        if max_sum < current_sum {
            max_sum = current_sum;
            max_start_index = current_start_index;
            max_end_index = current_index;
        }

        if current_sum < 0 {
            current_sum = 0;
            current_start_index = current_index + 1;
        }
    }

    input_array[max_start_index..=max_end_index].to_vec()
}

function bfMaximumSubarray(inputArray: number[]): number[] {
  let maxSubarrayStartIndex = 0;
  let maxSubarrayLength = 0;
  let maxSubarraySum: number | null = null;

  for (let startIndex = 0; startIndex < inputArray.length; startIndex += 1) {
    let subarraySum = 0;
    for (
      let arrLength = 1;
      arrLength <= inputArray.length - startIndex;
      arrLength += 1
    ) {
      subarraySum += inputArray[startIndex + (arrLength - 1)];
      if (maxSubarraySum === null || subarraySum > maxSubarraySum) {
        maxSubarraySum = subarraySum;
        maxSubarrayStartIndex = startIndex;
        maxSubarrayLength = arrLength;
      }
    }
  }

  return inputArray.slice(
    maxSubarrayStartIndex,
    maxSubarrayStartIndex + maxSubarrayLength,
  );
}

function dcMaximumSubarraySum(inputArray: number[]): number {
  function solveRecursively(elementIndex: number, mustPick: boolean): number {
    if (elementIndex >= inputArray.length) {
      return mustPick ? 0 : -Infinity;
    }
    return Math.max(
      inputArray[elementIndex] + solveRecursively(elementIndex + 1, true),
      mustPick ? 0 : solveRecursively(elementIndex + 1, false),
    );
  }

  return solveRecursively(0, false);
}

function dpMaximumSubarray(inputArray: number[]): number[] {
  let maxSum = -Infinity;
  let currentSum = 0;

  let maxStartIndex = 0;
  let maxEndIndex = inputArray.length - 1;
  let currentStartIndex = 0;

  inputArray.forEach((currentNumber, currentIndex) => {
    currentSum += currentNumber;

    if (maxSum < currentSum) {
      maxSum = currentSum;
      maxStartIndex = currentStartIndex;
      maxEndIndex = currentIndex;
    }

    if (currentSum < 0) {
      currentSum = 0;
      currentStartIndex = currentIndex + 1;
    }
  });

  return inputArray.slice(maxStartIndex, maxEndIndex + 1);
}