# Efficient Algorithms for the Maximum Sum Problems
## 2 Parallel Algorithms for the MSA Problem
### Parallel Algorithm 2  
This algorithm (Algorithm 3) does communication bi-directionally in a horizontal way. For simplicity, we assume \(n\) is even. The \((n,n)\) mesh is divided into two halves, left and right. The left half operates in the same way as Algorithm 2. The right half operates in a mirror image, that is control signals go from right to left initiated at the right border. All other data also flow from right to left. At the centre, that is at \((i,n/2)\), \(cell(i,n/2)\) performs \"\(centre[i]\gets max[i][n/2]+max[i][n/2+1]\)\", which adds the two values that are the sums of strip regions in the left and right whose heights are equal and, thus, can be added to form a possible solution crossing over the centre. At the end of the \(k\)-th iteration, all properties in Algorithm 2 hold on the left half, and the properties in the mirror image hold on the right half. In addition, we have that \(centre[i]\) is the value of the maximum subarray that lies above or that is touching the \(i\)-th row and crosses over the centre line.  
Figure 4: Illustration for Algorithm 2: The coverage of \(cell(i,j)\) at step \(k\).  
```
Initialization
```
1:for all\(0\leq i,j\leq n\) in parallel do
2:\(column[i][j]\gets 0;min[i][j]\leftarrow\infty\);
3:\(control[i][[j]\gets 0;sum[i][j]\gets 0\);
4:endfor
5:for\(0\leq i\leq n\) in parallel do
6:\(control[i][0]\gets 1;control[i][n+1]\gets 1\);
7:endfor
8: Main
9:for\(k\gets 1\) to \((3/2)n-1\)do
10:for all\(1\leq i,j\leq n\) in parallel do
11:if\(1\leq j\leq n/2\)then\(\triangleright\) left half
12:if\(control[i][j-1]=1\)then
13:\(column[i][j]\gets column[i-1][j]+a[i][j]\);
14:\(sum[i][j]\gets sum[i][j-1]+column[i][j]\);
15:\(min[i][j]\leftarrow\mathbb{MIN}\{min[i][j-1],sum[i][j]\}\);
16:\(max[i][j]\gets sum[i][j]-min[i][j]\);
17:\(sol[i][j]\leftarrow\mathbb{MAX}\{sol[i-1][j],sol[i][j-1],sol[i][j],max[i][j]\}\);
18:endif
19:endif
20:endif
21:if\(n/2+1\leq j\leq n\)then\(\triangleright\) right half
22:if\(control[i][j+1]=1\)then
23:\(column[i][j]\gets column[i-1][j]+a[i][j]\);
24:\(sum[i][j]\gets sum[i][j+1]+column[i][j]\);
25:\(min[i][j]\leftarrow\mathbb{MIN}\{min[i][j+1],sum[i][j]\}\);
26:\(max[i][j]\gets sum[i][j]-min[i][j]\);
27:\(sol[i][j]\leftarrow\mathbb{MAX}\{sol[i-1][j],sol[i][j+1],sol[i][j],max[i][j]\}\);
28:\(control[i][j]\gets 1\);
29:endif
30:endif
31:endif
32:if\(j=n/2\)then\(\triangleright\)\(cell(i,n/2)\) processes \(centre[i]\)
33:\(centre[i]\gets max[i][n/2]+max[i][n/2+1]\);
34:if\(centre[i]<centre[i-1]\)then
35:\(centre[i]\gets centre[i-1]\);
36:endif
37:endif
38:endfor
39:endfor
40: Finalization step
41: Let \(cell(n,n/2)\) do \(solution\leftarrow\mathbb{MAX}\{sol[n][n/2],sol[n][n/2+1],centre[n]\}\); ```
**Algorithm 3** MSA Parallel 2.  
The strip \(cell(i,j)\) processes is \(a[i+j-k,..,i][1,...,j]\) in the left half, and that in the right half is \(a[i+n-j+1-k,..,i][j,..,n]\). Thus, the cells \(cell(i,n/2)\) and \(cell(i,n/2+1)\) processes the strips of the same height in the left half and the right half. Communication steps are measured by the distance from \(cell(1,1)\) to \(cell(n,n/2)\) or, equivalently, from \(cell(1,n)\) to \(cell(n,n/2+1)\), which is \((3/2)n-1\). By adding the finalization step, we have \((3/2)n\) for the total communication steps.