Exercise 4.1-5

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 of A[1.. j] , extend the answer to find a maximum subarray ending at index j + 1 by using the following observation: a maximum subarray of A[1.. j + 1] is either a maximum subarray of A[1.. j] or a subarray A[i .. j +1] , for some 1 <= i<= 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.

Answer

First we need to figure out the maximum sub array ending at index j + 1 which could be just A[j + 1] or the maximum subarray ending at j plus A[j+1] , therefore we find the max of this two.

Once we have the maximum sub array ending at index j + 1 we find the maximum of A[1..j+1] by again, getting the max between  maximum sub array ending at index j + 1 and maximum subarray of A[1..j].

Code (C++):

void linearMaxSubArray(int*& ini, int*& fin){

    int sum = ini[0], max = ini[0],
        *inisum = ini, *end= fin;

    fin = ini + 1;
    for (auto i = ini + 1; i != end; ++i)
    {
        sum = std::max(*i, *i + sum);  
        inisum = sum == *i ? i : inisum;   
        if (sum > max)
        {
            fin = i + 1;
            ini = inisum;
            max = sum;
        }
    }
   
}

Problem 4-6 Monge arrays

Answers 

for a n x m matriz

a.

So we need to proof this:

The right implication is trivial as we can see that the left operand of the if only if is just a especial case of the monge definition. 

So to proof the left implication we assumed

and so we try to proof the monge definition by induction(fist on the rows as the hint suggested):

so we can use our assumption on k :

So using our inductive hypothesis we get:

For this to work l must be l=j+1 but when proving the same thing for the rows we then prove it for all possible k,l,j,i. 

b.

37 23 24 32 

21  6   7  10 

53 34 30 31 

32 13  9   6 

43 21 15  8

c. It can be proved by contradiction.

We make the assumption:  

being A[i,f(i)] and A[i+1,f(i+1)] the leftmost minimums, this must be false:

And so we prove it by contradiction 

d. 

This hold for all the odd rows:

So we just need to find the minimum between those bounds. 

The run time for finding all the leftmost minimums for the odd rows is given by the summation:

e.

Since each time the size is split to just the even rows and the merge step takes O(n+m), the run time
of the algorithm is given by the recurrence:

we analyse it using the recursion tree method and we can ignore the ceiling since it wont affect the asintotic behavior. The base case is O(1) since m is constant so assuming that n is a power of 2 there is lg(n) levels and each one takes m constant time so:

The code for the algorithm is:

C++

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37

int findMin(int* array, int init, int finale){ int index = 0; for (int min = INT_MAX; init < finale; ++init) { if (min > array[init]) { min = array[init]; index = init; } } return index; } void divideAndConquereMonge(int **matrizMonge, int* leftmost, int rows, int factor, int column){ if (rows == 1) leftmost[0] = findMin(matrizMonge[0], 0, column); else { int mid = static_cast<int>(std::ceil(rows / 2.0)); divideAndConquereMonge(matrizMonge, leftmost, mid, 2 * factor, column); for (int i = 1; i < rows - 1; i+= 2) { int dev = factor * i, end = leftmost[dev + factor] + 1; leftmost[dev] = findMin(matrizMonge[dev], leftmost[dev - factor], end); } if (rows % 2 == 0) { int dev = factor * (rows - 1); leftmost[dev] = findMin(matrizMonge[dev], leftmost[dev - factor], column); } } }

Rust 

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67

fn left_most_minimum(monge: &[i32], from: usize, to: usize) -> usize { let mut min = monge[from]; (from + 1..to).fold(from, |m,i| { if monge[i] < min { min = monge[i]; i } else { m } }) } fn minimums(monge: &[i32], leftmost: &mut Vec<usize>, rows: usize, columns: usize, factor: usize) { if rows == 1 { leftmost[0] = left_most_minimum(monge, 0, columns) % columns; } else { let mid = rows - (rows / 2); minimums(monge, leftmost, mid, columns, 2 * factor); let map = |i, j| (i * columns) + j; let x_rows = (0..) .map(|x| factor * (2 * x + 1)) .take_while(|&x| x < (rows - 1)); for row in x_rows { let (from, to) = (map(row, leftmost[row - factor]), map(row, leftmost[row + factor] + 1)); leftmost[row] = left_most_minimum(monge,from,to) % columns; } if rows % 2 == 0 { let row = factor * (rows - 1); let (from, to) = (map(row, leftmost[row - factor]), map(row, columns)); leftmost[row] = left_most_minimum(monge, from, to) % columns; } } } fn monge_left_most_minimums(monge: &[i32], rows: usize) -> Option<Vec<usize>> { let size = monge.len(); if rows == 0 || size % rows != 0 { return None; } let mut left_mosts = vec![0; rows]; minimums(&monge, &mut left_mosts, rows, size / rows, 1); Some(left_mosts) } fn main() { let row = 7; let monge = vec![ 10, 17, 13, 28, 23, 17, 22, 16, 29, 23, 24, 28, 22, 34, 24, 11, 13, 6, 17, 7, 45, 44, 32, 37, 23, 36, 33, 19, 21, 6, 75, 66, 51, 53, 34, ]; println!("{:?}", monge_left_most_minimums(&monge, row)); }