Maximum Sub-Array Problem Solution

Solving the problem
To solve the problem and to determine the maximum sub-array problem we used a modified version of Kadane’s algorithm.
How it Works
The modified Kadane’s algorithm has a cubic time complexity (O (n3)); it contains three main nested loops the outermost loop is responsible for determining the size of the sub-matrix the other loops works on, the second and the third loop are used to go over all the items in the sub matrix.
The algorithm divides the matrix to a number of sub-matrices, their sizes vary from a single row matrix to n row matrix; where n is the rows number; through every sub matrix we add the elements of this matrix row by row and store it in one-dimensional matrix and then apply Kadane’s algorithm on that array to determine the maximum of it. Then, the maximum sum from each sub-matrix is compared to determine the absolute sum.
Parallelize the Code
In parallelizing the problem we used the OpenMP libraries.
The problem for the outermost loop is unbalanced loads occurred as to parallelize it you have to consider that the inner loops will work on arrays of different sizes some are small as a one-dimensional array and others are large as the whole matrix to solve this problem we used the schedule clause of type (dynamic) and chunk size of 1. As there is a critical section at the end of the loop to determine the absolute sum so we added the (nowait) clause to increase the speed.
Handling all negative array
We were able to extend Kadane’s algorithm by finding the min while finding the maximum sum and in the end if the array is all negative you should return the minimum instead of maximum sum (which will now be zero).
Einzelheiten zur Compiler-Optimierung finden Sie in unserem Optimierungshinweis.
Kategorien: