准备面试写的 sample exercise...

Maximal Subarray Problem

Problem Description:

Given an one-dimensional array $a[1\dots n]$ consisting of either negative or positive integers, you need to find a non-empty continuous subarray $a[i\dots j]$ such its sum is maximal amony all subarrays. To simplify the task, only the sum itself is required.

Naive Solution in $O(n^3)$:

We simply enumerate all the subarrays and take the maximum. The procedure is as follows:

max_sum = -inf
for i in 1..n
    for j in i..n
        if sum(a[i..j]) > max_sum:
            max_sum = sum(a[i..j])

Smarter Recursive Solution in $O(n)$:

To get a more efficient algorithm, we have to utilise the underlying recursive structure of this problem.

Let $S[i]$ denote the maximal sum of subarrays ending at the $i$-th position. Why do we care about this? This is because that since the desired maximal subarray we are looking for must end somewhere between $1$ and $n$ (pretty trivial fact right?), its sum is just $\max(S[1],S[2],\cdots,S[n] )$. If we can calculate all the $S[i]$ fast, we are done. But how?

---

Firstly, let’s start from the easiest: $S[1]$. Since there is one and only one array ending at $1$, $S[1]$ is just $a[1]$.

---

Now assume we have found $S[i-1]$, how do we use this to calculate $S[i]$?

Here we split it into two cases:

Case 1: The length of the maximal subarray is $1$:

Easy! The sum is simply $a[i]$ because $a[i\dots i]$ is the unique subarray satisfies.

Case 2: The length of the maximal subarray is greater or equal to $2$:

Then the array can be considered as a concatenation of a subarray ending at the $i-1$ th position and $a[i]$. Since $a[i]$ is fixed, we only need to maximize the sum of the subarray ending at the $i-1$ th position. This is exactly what $S[i-1]$ is for!. Therefore, the sum in this case is $S[i-1]+a[i]$.

Hence, we have $S[i] = \max(a[i],S[i-1]+a[i])$.

---

Therefore, we get the following recursive relation:

$$S[i] = \begin{cases}a[1] & i = 1\\ \max(a[i],a[i]+S[i-1]) & \text{otherwise}\end{cases}$$

Example

Suppose the array $a[1\dots n] = [6, -1, 5, 4, -7]$

Stage	$a[i]$	$S[i]$	current max
$1$	$6$	$6$	$6$
$2$	$-1$	$5$	$6$
$3$	$5$	$10$	$10$
$4$	$4$	$14$	$14$
$5$	$-7$	$-7$	$14$

Therefore, the maximal subarray sum is $9$.

Task

Complete the following function:

def maxSum(a: [int], i):
    ···

Where $a$ is an array of integers and $i$ is the index. This function should return a pair of integers where the first entry is $S[i]$ and the second is the current max value as demonstrated in previous example. In this exercise you must write a recursive function to solve the problem i.e. no while or for loops in your program.

Solution

def maxSum(a: [int], i):
    if i == 0:
        return a[0], a[0]
    else:
        prevMax, curAns = maxSum(a, i - 1)
        curMax = max(a[i], a[i] + prevMax)
        return curMax, max(curMax, curAns)
print("Please inpunt an array of numbers:")
array = [int(i) for i in input().split()]
print("The maximal subarray sum is {}.".format(maxSum(array, len(array) - 1)[1]))