Hadron DaVinci

Find Min and Max Sum From Subarray

26 Dec 2020 - Hadron DaVinci

Problem

Given an array, create an algorithm which determines the minimum and maximum sum that can be obtained from any subarrays.

Examples

min_max([-2, -3, 4, -1, -2, 1, 5, -3]) == (-5, 7)

min_max([2, -1, -2, 1, -4, 2, 8]) == (-6, 10)

---

Methods

Method 1

Time Complexity: O(N^2)
Spatial Complexity: O(1)

Method 1 Summary

1. Create a generator that yields all sub arrays with contiguous elements
   • Note, total Time Complexity is N * N/2 = O(N^2)
   • Outer loop of generator will have Time Complexity of N
   • Inner loop of generator will have Time Complexity of N/2
     • Every inner loop reduces size of elements by 1
       which reduces the overall number of inner loop steps by half.
       See example:
     • Example given [1,2,3,4]:
       • elements analyzed not reducing size each time:
         • 1, 2, 3, 4
         • 1, 2, 3, 4
         • 1, 2, 3, 4
         • 1, 2, 3, 4
       • elements analyzed reducing size by 1 each time:
         • 1, 2, 3, 4
         • 1, 2, 3
         • 1, 2,
         • 1
2. Loop through each sub array:
   • Record the total
   • Update the min_sum
   • Update the max_sum
3. Return the min_sum and max_sum

Method 1 Solution

from typing import Generator

def sub_seq(s: list) -> Generator:
    """
    Returns sub contiguous sequences in s
    :param s: some sequence
    :return:
    """
    for i in range(0, len(s)):
        for j in range(i + 1, len(s) + 1):
            yield s[i: j]

def min_max(arr: list):
    min_sum = float('Inf')
    max_sum = float('-Inf')

    for s in sub_seq(arr):
        total = sum(s)
        min_sum = min(min_sum, total)
        max_sum = max(max_sum, total)

    return min_sum, max_sum

# Try Code
if __name__ == "__main__":
    assert min_max([-2, -3, 4, -1, -2, 1, 5, -3]) == (-5, 7)
    assert min_max([2, -1, -2, 1, -4, 2, 8]) == (-6, 10)
    assert min_max([-1, -1, -1]) == (-3, -1)

---

Method 2

Time Complexity: O(N)
Spatial Complexity: O(1)

Method 2 Summary

This approach uses a modified Kadane’s algorithm. Specifically, in this case, Kadane’s algorithm
has been modified so it can be used to calculate either a max or min from any subarray.
The key take-away here is when finding the min with Kadane’s algorithm, we must
(1) Subtract this_number from the running_total
(2) Return -1 * (best_sum)

Method 2 Steps

1. Use Kadane’s algorithm to calculate the min sum of any sub arrays
2. Use Kadane’s algorithm to calculate the max sum of any sub arrays
3. Return min sum and max sum

Method 2 Solution

def kadane(arr: list, get_max: bool) -> int:
    """
    Returns the max sum or min sum of sub arrays
    by keeping track of a running total.
    :param arr: a sequence
    :param get_max: when True, function returns max sum; otherwise returns min sum
    :return:
    """
    sign = -1
    if get_max:
        sign = 1

    best_sum = float('-inf')
    running_total = 0
    for this_number in arr:
        if running_total < 0:
            running_total = 0
        running_total = running_total + (sign * this_number)
        best_sum = max(best_sum, running_total)

    return best_sum * sign

def min_max(arr: list):
    min_sum = kadane(arr, False)
    max_sum = kadane(arr, True)
    return min_sum, max_sum

# Try Code
if __name__ == "__main__":
    assert min_max([-2, -3, 4, -1, -2, 1, 5, -3]) == (-5, 7)
    assert min_max([2, -1, -2, 1, -4, 2, 8]) == (-6, 10)
    assert min_max([-1, -1, -1]) == (-3, -1)

---

Files

method1.py
method2.py