4 added 92 characters in body edited Jun 6 at 9:30 Steven 89766 silver badges1111 bronze badges This is a polynomial time algorithm: Let $$S^*_j$$ be the sum of the the elements in the $$j$$-th subarray in an optimal solution and guess $$m^* = \min_j S^*_j$$ (there are only polynomially many choices of $$m^*$$). Given a a way to split an array into $$k$$ contiguous subarrays of sums $$S_1, \dots, S_k$$, define the cost of such a subdivision as: $$\begin{cases} \max_i S_i & \mbox{if } \min_i S_i \ge m^* \\ +\infty & \mbox{ otherwise.} \end{cases}$$ Let $$OPT_{m^*}[i,k]$$ the cost to split the array consisting of the first $$i$$ input elements into $$k$$ contiguous (non-empty) subarrays, and let $$x_i$$ be the $$i$$-th input element. Then, for $$i,k \ge 1$$, $$OPT_{m^*}[i][k] = \min_{j=0, \ldots, i-1} \begin{cases} \displaystyle\max\, \left\{ OPT_{m^*}[j][k-1], \sum_{h=j+1}^i x_i \right\} & \mbox{if } \displaystyle\sum_{h=j+1}^i x_i \ge m^* \\[10pt] +\infty & \mbox{otherwise} \end{cases}.$$ Where $$OPT_{m^*}[0][0] = 0$$ and $$OPT_{m^*}[i][0] = OPT_{m^*}[0][k] = +\infty$$ for all $$i,k > 0$$. The measure of an optimal solution to the original problem will be $$OPT_{m^*}[n][N] - m^*$$ and you can reconstruct where to split the input array using standard techniques (e.g., by inspecting the dynamic programming table in reverse order or by storing the value of $$j$$ chosen for each entry $$OPT_{m^*}[i][k]$$). Let $$S^*_j$$ be the sum of the the elements in the $$j$$-th subarray in an optimal solution and guess $$m^* = \min_j S^*_j$$. Given a a way to split an array into $$k$$ contiguous subarrays of sums $$S_1, \dots, S_k$$, define the cost of such a subdivision as: $$\begin{cases} \max_i S_i & \mbox{if } \min_i S_i \ge m^* \\ +\infty & \mbox{ otherwise.} \end{cases}$$ Let $$OPT_{m^*}[i,k]$$ the cost to split the array consisting of the first $$i$$ input elements into $$k$$ contiguous (non-empty) subarrays, and let $$x_i$$ be the $$i$$-th input element. Then, for $$i,k \ge 1$$, $$OPT_{m^*}[i][k] = \min_{j=0, \ldots, i-1} \begin{cases} \displaystyle\max\, \left\{ OPT_{m^*}[j][k-1], \sum_{h=j+1}^i x_i \right\} & \mbox{if } \displaystyle\sum_{h=j+1}^i x_i \ge m^* \\[10pt] +\infty & \mbox{otherwise} \end{cases}.$$ Where $$OPT_{m^*}[0][0] = 0$$ and $$OPT_{m^*}[i][0] = OPT_{m^*}[0][k] = +\infty$$ for all $$i,k > 0$$. The measure of an optimal solution to the original problem will be $$OPT_{m^*}[n][N] - m^*$$ and you can reconstruct where to split the input array using standard techniques (e.g., by inspecting the dynamic programming table in reverse order or by storing the value of $$j$$ chosen for each entry $$OPT_{m^*}[i][k]$$). This is a polynomial time algorithm: Let $$S^*_j$$ be the sum of the the elements in the $$j$$-th subarray in an optimal solution and guess $$m^* = \min_j S^*_j$$ (there are only polynomially many choices of $$m^*$$). Given a a way to split an array into $$k$$ contiguous subarrays of sums $$S_1, \dots, S_k$$, define the cost of such a subdivision as: $$\begin{cases} \max_i S_i & \mbox{if } \min_i S_i \ge m^* \\ +\infty & \mbox{ otherwise.} \end{cases}$$ Let $$OPT_{m^*}[i,k]$$ the cost to split the array consisting of the first $$i$$ input elements into $$k$$ contiguous (non-empty) subarrays, and let $$x_i$$ be the $$i$$-th input element. Then, for $$i,k \ge 1$$, $$OPT_{m^*}[i][k] = \min_{j=0, \ldots, i-1} \begin{cases} \displaystyle\max\, \left\{ OPT_{m^*}[j][k-1], \sum_{h=j+1}^i x_i \right\} & \mbox{if } \displaystyle\sum_{h=j+1}^i x_i \ge m^* \\[10pt] +\infty & \mbox{otherwise} \end{cases}.$$ Where $$OPT_{m^*}[0][0] = 0$$ and $$OPT_{m^*}[i][0] = OPT_{m^*}[0][k] = +\infty$$ for all $$i,k > 0$$. The measure of an optimal solution to the original problem will be $$OPT_{m^*}[n][N] - m^*$$ and you can reconstruct where to split the input array using standard techniques (e.g., by inspecting the dynamic programming table in reverse order or by storing the value of $$j$$ chosen for each entry $$OPT_{m^*}[i][k]$$). 3 improved formatting edited Jun 5 at 21:13 Steven 89766 silver badges1111 bronze badges Let $$S^*_j$$ be the sum of the the elements in the $$j$$-th subarray in an optimal solution and guess $$m^* = \min\limits_j S^*_j$$$$m^* = \min_j S^*_j$$. Given a a way to split an array into $$k$$ contiguous subarrays of sums $$S_1, \dots, S_k$$, define the cost of such a subdivision as: $$\begin{cases} \max\limits_i S_i & \mbox{if } \min\limits_i S_i \ge m^* \\ +\infty & \mbox{ otherwise.} \end{cases}$$$$\begin{cases} \max_i S_i & \mbox{if } \min_i S_i \ge m^* \\ +\infty & \mbox{ otherwise.} \end{cases}$$ Let $$OPT_{m^*}[i,k]$$ the cost to split the array consisting of the first $$i$$ input elements into $$k$$ contiguous (non-empty) subarrays, and let $$x_i$$ be the $$i$$-th input element. Then, for $$i,k \ge 1$$, $$OPT_{m^*}[i][k] = \min_{j=0, \ldots, i-1} \begin{cases} \max\, \{ OPT_{m^*}[j][k-1], \sum_{h=j+1}^i x_i \} & \mbox{if } \sum_{h=j+1}^i x_i \ge m^* \\ +\infty & \mbox{otherwise} \end{cases}.$$$$OPT_{m^*}[i][k] = \min_{j=0, \ldots, i-1} \begin{cases} \displaystyle\max\, \left\{ OPT_{m^*}[j][k-1], \sum_{h=j+1}^i x_i \right\} & \mbox{if } \displaystyle\sum_{h=j+1}^i x_i \ge m^* \\[10pt] +\infty & \mbox{otherwise} \end{cases}.$$ Where $$OPT_{m^*}[0][0] = 0$$ and $$OPT_{m^*}[i][0] = OPT_{m^*}[0][k] = +\infty$$ for all $$i,k > 0$$. The measure of an optimal solution to the original problem will be $$OPT_{m^*}[n][N] - m^*$$ and you can reconstruct where to split the input array using standard techniques (e.g., by inspecting the dynamic programming table in reverse order or by storing the value of $$j$$ chosen for each entry $$OPT_{m^*}[i][k]$$). Let $$S^*_j$$ be the sum of the the elements in the $$j$$-th subarray in an optimal solution and guess $$m^* = \min\limits_j S^*_j$$. Given a a way to split an array into $$k$$ contiguous subarrays of sums $$S_1, \dots, S_k$$, define the cost of such a subdivision as: $$\begin{cases} \max\limits_i S_i & \mbox{if } \min\limits_i S_i \ge m^* \\ +\infty & \mbox{ otherwise.} \end{cases}$$ Let $$OPT_{m^*}[i,k]$$ the cost to split the array consisting of the first $$i$$ input elements into $$k$$ contiguous (non-empty) subarrays, and let $$x_i$$ be the $$i$$-th input element. Then, for $$i,k \ge 1$$, $$OPT_{m^*}[i][k] = \min_{j=0, \ldots, i-1} \begin{cases} \max\, \{ OPT_{m^*}[j][k-1], \sum_{h=j+1}^i x_i \} & \mbox{if } \sum_{h=j+1}^i x_i \ge m^* \\ +\infty & \mbox{otherwise} \end{cases}.$$ Where $$OPT_{m^*}[0][0] = 0$$ and $$OPT_{m^*}[i][0] = OPT_{m^*}[0][k] = +\infty$$ for all $$i,k > 0$$. The measure of an optimal solution to the original problem will be $$OPT_{m^*}[n][N] - m^*$$ and you can reconstruct where to split the input array using standard techniques (e.g., by inspecting the dynamic programming table in reverse order or by storing the value of $$j$$ chosen for each entry $$OPT_{m^*}[i][k]$$). Let $$S^*_j$$ be the sum of the the elements in the $$j$$-th subarray in an optimal solution and guess $$m^* = \min_j S^*_j$$. Given a a way to split an array into $$k$$ contiguous subarrays of sums $$S_1, \dots, S_k$$, define the cost of such a subdivision as: $$\begin{cases} \max_i S_i & \mbox{if } \min_i S_i \ge m^* \\ +\infty & \mbox{ otherwise.} \end{cases}$$ Let $$OPT_{m^*}[i,k]$$ the cost to split the array consisting of the first $$i$$ input elements into $$k$$ contiguous (non-empty) subarrays, and let $$x_i$$ be the $$i$$-th input element. Then, for $$i,k \ge 1$$, $$OPT_{m^*}[i][k] = \min_{j=0, \ldots, i-1} \begin{cases} \displaystyle\max\, \left\{ OPT_{m^*}[j][k-1], \sum_{h=j+1}^i x_i \right\} & \mbox{if } \displaystyle\sum_{h=j+1}^i x_i \ge m^* \\[10pt] +\infty & \mbox{otherwise} \end{cases}.$$ Where $$OPT_{m^*}[0][0] = 0$$ and $$OPT_{m^*}[i][0] = OPT_{m^*}[0][k] = +\infty$$ for all $$i,k > 0$$. The measure of an optimal solution to the original problem will be $$OPT_{m^*}[n][N] - m^*$$ and you can reconstruct where to split the input array using standard techniques (e.g., by inspecting the dynamic programming table in reverse order or by storing the value of $$j$$ chosen for each entry $$OPT_{m^*}[i][k]$$). 2 improved formatting edit approved Jun 5 at 21:13 user2052436 11333 bronze badges Let $$S^*_j$$ be the sum of the the elements in the $$j$$-th subarray in an optimal solution and guess $$m^* = \min_j S^*_j$$$$m^* = \min\limits_j S^*_j$$. Given a a way to split an array into $$k$$ contiguous subarrays of sums $$S_1, \dots, S_k$$, define the cost of such a subdivision as: $$\begin{cases} \max_i S_i & \mbox{if } \min_i S_i \ge m^* \\ +\infty & \mbox{ otherwise.} \end{cases}$$$$\begin{cases} \max\limits_i S_i & \mbox{if } \min\limits_i S_i \ge m^* \\ +\infty & \mbox{ otherwise.} \end{cases}$$ Let $$OPT_{m^*}[i,k]$$ the cost to split the array consisting of the first $$i$$ input elements into $$k$$ contiguous (non-empty) subarrays, and let $$x_i$$ be the $$i$$-th input element. Then, for $$i,k \ge 1$$, $$OPT_{m^*}[i][k] = min_{j=0, \dots, i-1} \begin{cases} \max \{ OPT_{m^*}[j][k-1], \sum_{h=j+1}^i x_i \} & \mbox{if } \sum_{h=j+1}^i x_i \ge m^* \\ +\infty & \mbox{otherwise} \end{cases}.$$$$OPT_{m^*}[i][k] = \min_{j=0, \ldots, i-1} \begin{cases} \max\, \{ OPT_{m^*}[j][k-1], \sum_{h=j+1}^i x_i \} & \mbox{if } \sum_{h=j+1}^i x_i \ge m^* \\ +\infty & \mbox{otherwise} \end{cases}.$$ Where $$OPT_{m^*}[0][0] = 0$$ and $$OPT_{m^*}[i][0] = OPT_{m^*}[0][k] = +\infty$$ for all $$i,k > 0$$. The measure of an optimal solution to the original problem will be $$OPT_{m^*}[n][N] - m^*$$ and you can reconstruct where to split the input array using standard techniques (e.g., by inspecting the dynamic programming table in reverse order or by storing the value of $$j$$ chosen for each entry $$OPT_{m^*}[i][k]$$). Let $$S^*_j$$ be the sum of the the elements in the $$j$$-th subarray in an optimal solution and guess $$m^* = \min_j S^*_j$$. Given a a way to split an array into $$k$$ contiguous subarrays of sums $$S_1, \dots, S_k$$, define the cost of such a subdivision as: $$\begin{cases} \max_i S_i & \mbox{if } \min_i S_i \ge m^* \\ +\infty & \mbox{ otherwise.} \end{cases}$$ Let $$OPT_{m^*}[i,k]$$ the cost to split the array consisting of the first $$i$$ input elements into $$k$$ contiguous (non-empty) subarrays, and let $$x_i$$ be the $$i$$-th input element. Then, for $$i,k \ge 1$$, $$OPT_{m^*}[i][k] = min_{j=0, \dots, i-1} \begin{cases} \max \{ OPT_{m^*}[j][k-1], \sum_{h=j+1}^i x_i \} & \mbox{if } \sum_{h=j+1}^i x_i \ge m^* \\ +\infty & \mbox{otherwise} \end{cases}.$$ Where $$OPT_{m^*}[0][0] = 0$$ and $$OPT_{m^*}[i][0] = OPT_{m^*}[0][k] = +\infty$$ for all $$i,k > 0$$. The measure of an optimal solution to the original problem will be $$OPT_{m^*}[n][N] - m^*$$ and you can reconstruct where to split the input array using standard techniques (e.g., by inspecting the dynamic programming table in reverse order or by storing the value of $$j$$ chosen for each entry $$OPT_{m^*}[i][k]$$). Let $$S^*_j$$ be the sum of the the elements in the $$j$$-th subarray in an optimal solution and guess $$m^* = \min\limits_j S^*_j$$. Given a a way to split an array into $$k$$ contiguous subarrays of sums $$S_1, \dots, S_k$$, define the cost of such a subdivision as: $$\begin{cases} \max\limits_i S_i & \mbox{if } \min\limits_i S_i \ge m^* \\ +\infty & \mbox{ otherwise.} \end{cases}$$ Let $$OPT_{m^*}[i,k]$$ the cost to split the array consisting of the first $$i$$ input elements into $$k$$ contiguous (non-empty) subarrays, and let $$x_i$$ be the $$i$$-th input element. Then, for $$i,k \ge 1$$, $$OPT_{m^*}[i][k] = \min_{j=0, \ldots, i-1} \begin{cases} \max\, \{ OPT_{m^*}[j][k-1], \sum_{h=j+1}^i x_i \} & \mbox{if } \sum_{h=j+1}^i x_i \ge m^* \\ +\infty & \mbox{otherwise} \end{cases}.$$ Where $$OPT_{m^*}[0][0] = 0$$ and $$OPT_{m^*}[i][0] = OPT_{m^*}[0][k] = +\infty$$ for all $$i,k > 0$$. The measure of an optimal solution to the original problem will be $$OPT_{m^*}[n][N] - m^*$$ and you can reconstruct where to split the input array using standard techniques (e.g., by inspecting the dynamic programming table in reverse order or by storing the value of $$j$$ chosen for each entry $$OPT_{m^*}[i][k]$$). 1 answered Jun 4 at 18:55 Steven 89766 silver badges1111 bronze badges