# Efficient Algorithms for the Maximum Sum Problems
## 1 Introduction  
We face a challenge to process a big amount of data in the age of information explosion and big data [1]. As the end of [PERSON]'s law comes in sight, however, the extra computing power is unlikely obtained from a single processor computer [2]. Parallel computing is obviously a direction to faster computation. However, efficient utilization of the parallel architecture is not an effortless task. New algorithms often need to be designed for specific problems on specific hardware. In this paper, we investigate the maximum subarray (MSA) problem and the maximum convex sum (MCS) problem, the latter being a generalization of the former. We design efficient parallel algorithms for both problems and an improved sequential algorithm for the MCS problem. The MSA problem is to find a rectangular subarray in the given two-dimensional (2D) data array that maximizes the sum in it. This problem has wide applications from image processing to data mining. An example application from image processing is to find the most distinct spot, such as brightest or darkest, in the given image. If all pixel values are non-negative, solving the MSA problem will return the trivial solution of the whole array. Thus, we normalize the input image (e.g., by subtracting the mean value), such that the relatively brighter spots will have positive sums, while the relatively darker spots will have negative sums. Then, solving the MSA problem on the normalized image can give us the brightest spot in the image. In data mining, suppose we spread the sales amounts of some product on a two-dimensional array classified by customer ages and annual income. Then, after normalizing the data, the maximum subarray corresponds to the most promising customer range. We now consider the MCS problem that maximizes the sum in a convex shape. The definition of the word \"convex\" is not exactly the same as that in geometry. We define the convex shape as thejoining of a \(W\)-shape and an \(N\)-shape, where \(W\) stands for widening and \(N\) for narrowing. We call this shape the \(WN\)-convex shape or \(WN\)-shape for short. In \(W\), the top boundary goes up or stays horizontal when scanned from left to right, and the bottom boundary goes down or stays horizontal. [PERSON] et al. defines a more general rectilinear shape [3], but for simplicity, we only consider the \(WN\)-shape. The paper is mainly devoted to computing the maximum sum, and one section is devoted to the computation of the explicit convex shape that provides the sum. We give an example to illustrate how solving the MCS problem can provide a much more accurate data analysis compared to solving the MSA problem. We compared the size of the hole in the ozone layer over Antarctica between 2006 and 2011 by solving both the MSA problem and the MCS problem on the normalized input images (Figure 1a,d, respectively) of the Antarctic region. Figure 1b,e is from solving the MSA problem on the input images, while Figure 1c,f is from solving the MCS problem on the same set of input images. Solving the MCS problem clearly provides a much more accurate representation of the ozone hole. The numeric value returned by the MCS is also 22%-24% greater than that by the MSA on both occasions. Intuitively similar gains from the \(WN\)-shape compared to the rectangular shape can be foreseen for other types of data analysis. In this paper, we assume that the input data array is an \((n,n)\) square two-dimensional (2D) array. It is a straightforward exercise to extend the contents of this paper to \((n,m)\) rectangular 2D input data arrays. The typical algorithm for the MSA problem by [PERSON] [4] takes \(O(n^{3})\) time on a sequential computer. This has been improved to a slightly sub-cubic time bound by [PERSON] and [PERSON] [5] and also [PERSON] [6]. For the MCS problem, an algorithm with \(O(n^{3})\) time is given by [PERSON] et al. [3], and an algorithm with a sub-cubic time bound is not known. [PERSON] discussed a parallel implementation to solve the MSA problem on a PRAM [6].