Maximum Subarray Problem: Design and Analysis of New Sequential and Parallel Algorithms

The maximum subarray problem, a classic problem in computer science, involves identifying and locating a contiguous random-sized segment that contains the largest possible sum. This is an abstraction of a number of application domains, such as locating brightest areas in images, a sequencing problem in genomics and a data mining problem. Built upon a variety of known algorithmic methods, a number of efficient new sequential algorithms for an extended version of the original problem (K>1) are designed and analysied mathematically and empirically. The empirical evaluation of each new sequential algorithm is mostly consistent with the theoretical worst case time complexity. Previous parallel algorithms for the 2D problem have huge demand for hardware resources, or their target parallel computation models are in the realm of pure theoretics. Two new parallal algorithms based on the mesh topology offer a good compromise between speed and cost and greater potential for practical applications.