# Efficient Algorithms for the Maximum Sum Problems
## 2 Parallel Algorithms for the MSA Problem
### Parallel Algorithm 3  
In Algorithm 4, data flow in four directions. The array is divided into two halves; left and right, as in the previous section. Column sums \(c\) and prefix sums \(s\) accumulate downwards as before, whereas column sums \(d\) and prefix sums \(t\) accumulate upwards. See Figure 5.
```
1:for all\(0\leq i,j\leq n+1\) in parallel do
2:\(c[i][j]\gets 0;\bar{d}[i][j]\gets 0\);
3:\(min[i][j]\leftarrow\infty;control[i][[j]\gets 0\);
4:\(s[i][j]\gets 0;t[i][j]\gets 0\);
5:endfor
6:for\(0\leq i\leq n+1\) in parallel do
7:\(control[i][0]\gets 1;control[i][n+1]\gets 1\);
8:endfor
9:for\(k\gets 1\) to \(n-2\)do
10:for all\(1\leq i,j\leq n\) in parallel do
11:if\(1\leq j\leq n/2\)then
12:if\(control[i][j-1]=1\)then
13:\(c[i][j]\gets c[i-1][j]+a[j]\);
14:\(s[i][j]\gets s[i][j-1]+c[i][j]\);
15:\(d[i][j]\gets d[i-1][j]+a[i]\);
16:\(t[i][j]\gets t[i][j-1]+d[i][j]\);
17:\(u[i][j]\gets s[i][j]+t[i+1][j]\);
18:\(min[i][j]\leftarrow\mathrm{M}\mathbbm{N}\{min[i][j-1],u[i][j]\}\);
19:\(max[i][j]\gets u[i][j]-min[i][j]\);
20:\(sol[i][j]\leftarrow\mathrm{M}\mathbbm{A}\{sol[i-1][j],sol[i+1][j],sol[i][j-1], sol[i][j]\}\);
21:\(sol[i][j]\leftarrow\mathrm{M}\mathbbm{A}\{sol[i][j],max[i][j]\}\);
22:\(control[i][j]\gets 1\);
23:endif
24:endif
25:if\(n/2+1\leq j\leq n\)then
26:if\(control[i][j+1]=1\)then
27:\(c[i][j]\gets c[i-1][j]+a[i][j]\);
28:\(s[i][j]\gets s[i][j+1]+c[i][j]\);
29:\(d[i][j]\gets d[i+1][j]+a[i]\);
30:\(t[i][j]\gets t[i][j]+d[i][j]\);
31:\(u[i][i]\gets s[i][j]+t[i+1][j]\);
32:\(min[i][j]\leftarrow\mathrm{M}\mathbbm{N}\{min[i][j+1],u[i][j]\}\);
33:\(max[i][j]\gets u[i][j]-min[i][j]\);
34:\(sol[i][j]\leftarrow\mathrm{M}\mathbbm{A}\{sol[i-1][j],sol[i+1][j],sol[i][j+1], sol[i][j]\}\);
35:\(sol[i][j]\leftarrow\mathrm{M}\mathbbm{A}\{sol[i][j],max[i][j]\}\);
36:\(control[i][j]\gets 1\);
37:endif
38:endif
39:endif
40:endif
41:endfor
42:endfor
43:if\(i=n/2\) and \(j=n/2\)then
44:\(solution\leftarrow\mathrm{M}\mathbbm{A}\{sol[n/2][n/2],sol[n/2][n/2+1], centre[n/2]\}\);
45:endif
46:endif
47:endif
48:endfor
49:endfor
50:if\(i=n/2\) and \(j=n/2\)then
51:\(solution\leftarrow\mathrm{M}\mathbbm{A}\{sol[n/2][n/2],sol[n/2][n/2+1], centre[n/2]\}\);



The structure of Algorithm 4 reveals that at the end of the \(k\)-th iteration, \(s[i][j]\) is the sum of \(a[i+j-k,...,i][1,...,j]\) and \(t[i+1][j]\) is the sum of \(a[i+1,...,i-j+k+1][1,...,j]\). The height of each subarray is \(k-j+1\). Since the widths of those two areas are the same, we can have the prefix sum \(u[i][j]=s[i][j]+t[i+1][j]\) that covers \(a[i+j-k,...,i-j+k+1][1,...,j]\), the height of which is \(2(k-j+1)\). That is, spending \(k\) steps, we can achieve twice as much height as that in Algorithm 3. The solution array \(sol\) is calculated as before, but the result is sent into three directions; up, down and right in the left half and up, down and left in the right half. We have the property that \(sol[i][j]\) is the maximum sum in subarray \(a[i+j-k,...,i-j+k+1][1,...,j]\) in the left half. Substituting \(i=n/2,j=n/2\), and \(k=n-1\) yields the subarray \(a[1,...,n][1,...,n/2]\). Similarly, \(sol[n/2][n/2+1]\) is the maximum sum in the subarray \(a[1,...,n][n/2+1,...,n]\). For simplicity, we deal with the maximum subarray whose height is an even number. For a general case, see the note at the end of this section. The computation proceeds with \(n-2\) steps by \(k\) and the last step of comparing the results from \(cell(n/2,n/2)\) and \(cell(n/2+1,n/2)\), resulting in \(n-1\) steps in total. Note that we described the algorithm for the solution whose height is an even number. This fact comes from the assignment statement \"\(u[i][j]\gets s[i][j]+t[i+1][j]\)\" where the heights of subarrays whose sums are \(s\) and \(t\) are equal. To accommodate a height of an odd number, we can use the value of \(t\) one step before, whose height is one shorter. To accommodate such odd heights, we need to almost double the size of the program by increasing the number of variables.