Based on this recurrence relation arrive at an iterative algorithm. Derive the run time of your algorithm. Note that your algorithm need not output a max-cost cut, it suffices to output only its cost.

Let M be a matrix of integers with n rows and m columns and let J] denote the entry in ith row and jth column. Both rows and columns are indexed from 1. A horizontal cut in M is a sequence c,c2,... ,cm] such that For every i. 1