# Efficient Algorithms for the Maximum Sum Problems
## 5 Parallel Algorithm for MCS
: For \(\{P(k-1)\}cell(i,j)\{P_{1}(k)\}\): At time \(k-1\), \(column[i-1][j]=sum(i-1+j\ -\ (k-1),...,i-1;j)=sum(i+j-k,...,i-1;j)\). \"\(column[i][j]\gets column[i-1][j]+a[i][j]\)\" is performed for \(i=1,...,n\) and \(j=1,...,k\) in parallel. Thus, \(\{P(k-1)\}cell(i,j)\{P_{1}(k)\}\) holds. Proof. : For \(\{P(k-1)\}cell(i,j)\{P_{2}(k)\}\): At time \(k-1\), \(top[i-1][j]=a[i+j-1-(k-1)][j]=a[i+j-k][j]\). At time \(k\), \"\(top[i][j]\gets top[i-1][j]\)\" is performed for \(i=1,...,n\) and \(j=1,...,k\) in parallel. Thus, \(top[i][j]=a[i+j-k][j]\), and \(\{P(k-1)\}cell(i,j)\{P_{2}(k)\}\) holds. Proof. : For \(\{P(k-1)\}cell(i,j)\{P_{3}(k)\}\): At time \(k-1\), \(W[i][j-1]\) is the maximum of \(W\)-shapes anchored at column \(a[i+(j-1)-(k-1),...,i][j-1]=a[i+j-k,...,i][j-1]\). By adding the sum of column \(a[i+j-k,...,i][j]\), \(cand_{1}\) is made. \(W[i-1][j]\) is the maximum of the \(W\)-shape anchored at column \(a[i-1+j-(k-1),...,i-1][j]=a[i+j-k,...,i-1][j]\). By adding \(a[i][j]\), \(cand_{2}\) is made. \(old\_W[i][j]\) is \(W[i][j]\) at time \(k-1\), which is the maximum of \(W\)-shapes anchored at column \(a[i+j-(k-1),...,i][j]=a[i+j-k+1][j]\). By adding \(top[i][j]=a[i+j-k][j]\), \(cand_{3}\) is made. Since the maximum of the \(W\)-shape based on column \(a[i+j-k,...,i][j]\) is chosen from only those three possibilities, \(W[i][j]\) is correctly computed. Proof. : For \(\{P(k-1)\}cell(i,j)\{P_{4}(k)\}\): After \(cell(i,j)\), the value of \(old\_W[i][j]\) changes from \(W[i][j]\) at \(k-2\) to \(k-1\). Thus, \(\{P(k-1)\}cell(i,j)\{P_{4}(k)\}\) holds. Proof. : For \(\{P(k-1)\}cell(i,j)\{P_{5}(k)\}\): The scopes for the four candidates are given below. \(\bullet\)\(sol[i-1][j]\) at \(k-1\): \(scope[i-1+j-(k-1),...,i-1][1,...,j]=scope[i+j-k,...,i-1][1,...,j]\)

\(\bullet\)\(sol[i][j-1]\) at \(k-1\): \(scope[i+(j-1)-(k-1).i][1,...,j-1]=scope[i+j-k,...,i][1,...,j-1]\)

\(\bullet\)\(sol[i][j]\) at \(k-1\): \(scope[i+j-(k-1),...,i][1,...,j]=scope[i+j-k+1,...i][1,...,j]\)

\(\bullet\)\(W[i][j]\) at \(k\) is anchored at column \(a[i+j-k,...,i][j]\) with \(scope[i+j-k,...,i][1,...,j]\)

\(\Box\)

There are only four candidates for \(sol[i][j]\) from those four scopes. Thus, \(\{P(k-1)\}cell(i,j)\{P_{5}(k)\}\) holds. **Acknowledgments:** This research was supported by the EU/NZ Joint Project, Optimization and its Applications in Learning and Industry (OptALI). The experiments were conducted utilising high performance computing resources from the New Zealand eScience Infrastructure (NeSI), especially the High Performance Computing unit at the University of Canterbury (UCHPC). [NeSI-UCHPC]URL [[https://www.nesi.org.nzonhttp://www.hpc.canterbury.ac.nz](https://www.nesi.org.nzonhttp://www.hpc.canterbury.ac.nz)]([https://www.nesi.org.nzonhttp://www.hpc.canterbury.ac.nz](https://www.nesi.org.nzonhttp://www.hpc.canterbury.ac.nz))

**Author Contributions:** All authors contributed to the design of algorithms; [PERSON] provided the codes; [PERSON] and [PERSON] designed and performed the experiments; [PERSON] provided the formal proofs; [PERSON] provided the figures; [PERSON] wrote more of the initial draft, and all authors contributed to the finalization of the paper

**Conflicts of Interest:** The authors declare no conflict of interest. ## References

* (1) [PERSON] [PERSON] [PERSON]: Beyond the data deluge. _Science_**2009**, _323_, 1297-1298. * (2) [PERSON] The search for a new machine. _Sci. Am._**2015**, _312_, 48-53. * (3) [PERSON]; [PERSON]; [PERSON]; [PERSON] Data mining with optimized two-dimensional association rules. _ACM Trans. Database Syst._**2001**, _26_, 179-213. * (4) [PERSON] Perspective on performance. _Commun. ACM_**1984**, _27_, 1087-1092. * (5) [PERSON]; [PERSON] Algorithms for the maximum subarray problem based on matrix multiplication. In Proceedings of the 9 th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 1998), San Francisco, CA, USA, 25-27 January 1998; pp. 446-452. * (6) [PERSON] Efficient algorithms for the maximum subarray problem by distance matrix multiplication. _Electr. Notes Theor. Comput.