A simple program that implements four algorithms to compute the Maximum Subarray Problem (old school project, Complexity class, 2017).

Complexity

Naive algorithm in
Optimized version of naive algorithm in
Divide-and-conquer algorithm in
Kadane's algorithm in

Usage

mkdir obj && mkdir bin && make
./bin/maximum_subarray --help

Usage: ./bin/maximum_subarray <algorithm> <input> <options>

Algorithms: --naive | --naive_opti | --divide_conquer | --kadane
--naive: compute the maximum subarray using a naive approch. O(n³)
--naive_opti: compute the maximum subarray using a naive approch and applying a simple optimization S(k,l) = S(k,l-1) + T[l].
--divide_conquer: compute the maximum subarray by dividing recursively the problem by applying the divide-and-conquer paradigm.
--kadane: compute the maximum subarray in linear time using the Kadane's algorithm.

Inputs: ((-i | --stdin) <n0..ni>) | ((-r | --random) <size>) | ((-f | --file) <file_name>)
-i ou --stdin: the sequence is write in the command line, surrounded by " where each element is separated with a space.
-r ou --random: the sequence is randomly generated, with a specified size.
-f ou --file: the sequence is provide by a file, where each element where each element is separated with a space.

-h ou --help: print the current usage.
-a ou --print: print the input sequence and the ouput subsequence.
-g ou --gen_random: generate a random sequence of size n in a file called 'random'.
-t ou --test: execute a serie of test by comparing algorithms outputs with known results

Using the code

#include "maximum_subarray.h"

int *T, n, k, l, sum;

/* Fill T and n */
/* [...] */

sum = maximum_subarray_kadane(T, n, &k, &l);

Experiments

On the naive algorithm with an input of size 1K:

./bin/maximum_subarray --naive --random 1000
Generation of the sequence in 0.001s.
Execution of the algorithm in 0.886747s.

On the optimized naive algorithm with an input of size 1K:

./bin/maximum_subarray --naive_opti --random 1000
Generation of the sequence in 0.001s.
Execution of the algorithm in 0.001820s.

On the divide and conquer algorithm with an input of size 1K:

./bin/maximum_subarray --divide_conquer --random 1000
Generation of the sequence in 0.001s.
Execution of the algorithm in 0.000187s.

On the Kadane's algorithm with an input of size 1K:

./bin/maximum_subarray --kadane --random 1000
Generation of the sequence in 0.001s.
Execution of the algorithm in 0.000009s.

On the Kadane's algorithm with an input of size 10K:

./bin/maximum_subarray --kadane --random 10000
Generation of the sequence in 0.007s.
Execution of the algorithm in 0.000037s.

On the Kadane's algorithm with an input of size 100K:

./bin/maximum_subarray --kadane --random 100000
Generation of the sequence in 0.056s.
Execution of the algorithm in 0.000310s.

On the Kadane's algorithm with an input of size 1M:

./bin/maximum_subarray --kadane --random 1000000
Generation of the sequence in 0.495s.
Execution of the algorithm in 0.003076s.

Authors

• Charly Lamothe
• Doulkifouli Abdallah-Ali