# Exercise 4.1.5

Use the following ideas to develop a nonrecursive, linear-time algorithm for the maximum-subarray problem. Start at the left end of the array, and progress toward the right, keeping track of the maximum subarray seen so far. Knowing a maximum subarray $A[1..j]$, extend the answer to find a maximum subarray ending at index $j + 1$ by using the following observation: a maximum subarray $A[i..j+1]$, for some $1 \leq i \leq j + 1$. Determine a maximum subarray of the form $A[i..j+1]$ in constant time based on knowing a maximum subarray ending at index $j$.

We need to build an array $S$ that holds the maximum subarrays ending on each index of $A$. That is, $S[j]$ holds information about the maximum subarray ending on $j$.

We first loop through the input to build $S$. Afterwards, we do what they suggest in the text. This is $n + n = 2n = \Theta(n)$.

### C code

typedef struct {
unsigned left;
unsigned right;
int sum;
} max_subarray;

max_subarray find_maximum_subarray(int A[], unsigned low, unsigned high) {
max_subarray suffixes[high - low];

suffixes[0].left = low;
suffixes[0].right = low + 1;
suffixes[0].sum = A[low];

for (int i = low + 1; i < high; i++) {
if (suffixes[i - 1].sum < 0) {
suffixes[i].left = i;
suffixes[i].right = i + 1;
suffixes[i].sum = A[i];
} else {
max_subarray *previous = &suffixes[i - 1];
suffixes[i].left = previous->left;
suffixes[i].right = i + 1;
suffixes[i].sum = previous->sum + A[i];
}
}

max_subarray *max = &suffixes[0];

for (int i = low + 1; i < high; i++) {
if (max->sum < suffixes[i].sum) {
max = &suffixes[i];
}
}

return *max;
}