Revisions to Array segmenting algorithm

added 1 character in body

Source Link

edited Mar 14, 2020 at 17:52

29.6k
2
28
49

From a quick look at your problem, it seems that it can be solved in $O(nk)$ time using dynamic programming.

Let $[a_1, \dots, a_n]$ be your input array and define $\delta(i,j)$ as the minimum sum of the differences between the first and last element of each segment in an optimal subdivision of $[a_1, \dots, a_i]$ into at most $j$ segments. If no feasible subdivision exists then let $\delta(i,j) = +\infty$.

Then:

$\delta(0,j)=0$ for any $j \ge 0$;
$\delta(i,0)=+\infty$ for $i>0$; and
$\delta(i,j) = \min_{\substack{h = 1, \dots, i \\ a_i - a_h < 125}} \big\{ \delta(h-1, j-1) + a_i - a_h \big\}$, for $i,j>0$ (where the minimum over an empty set is $+\infty$).

The value of the optimal solution is $\delta(n, k)$ and, since computing each $\delta(i,j)$ requires $O(1)$ time, the overall time required is $O(nk)$. The optimal solution can be reconstructed using standard techniques (e.g., by retracing the optimal choices backwards, or by storing -for each $\delta(i,j)$- the optimal value of $h$ in the minimum).

There isn't much different between the above description an the pseudocode of the algorithm:

Let A[1],...,A[n] be the elements of the input array.
Let delta be a (n+1)x(k+1) matrix of integers, whose entries are indexed from 0 and initialized with -1 (representing +infinity);

for j=0,...,k:
    delta[0][j]=0;

for i=1,...,n:
    for j=1,...,k:
        for h=i,i-1,...,1:
            if A[i] - A[h]>125A[h]>=125: break;
            if delta[h-1][j-1]!=-1 and (delta[i][j]==-1 or delta[h-1][j-1] + A[i] - A[h] < delta[i][j]):
                delta[i][j] = delta[h-1][j-1] + A[i] - A[h];

return delta[n][k];

From a quick look at your problem, it seems that it can be solved in $O(nk)$ time using dynamic programming.

Let $[a_1, \dots, a_n]$ be your input array and define $\delta(i,j)$ as the minimum sum of the differences between the first and last element of each segment in an optimal subdivision of $[a_1, \dots, a_i]$ into at most $j$ segments. If no feasible subdivision exists then let $\delta(i,j) = +\infty$.

Then:

$\delta(0,j)=0$ for any $j \ge 0$;
$\delta(i,0)=+\infty$ for $i>0$; and
$\delta(i,j) = \min_{\substack{h = 1, \dots, i \\ a_i - a_h < 125}} \big\{ \delta(h-1, j-1) + a_i - a_h \big\}$, for $i,j>0$ (where the minimum over an empty set is $+\infty$).

The value of the optimal solution is $\delta(n, k)$ and, since computing each $\delta(i,j)$ requires $O(1)$ time, the overall time required is $O(nk)$. The optimal solution can be reconstructed using standard techniques (e.g., by retracing the optimal choices backwards, or by storing -for each $\delta(i,j)$- the optimal value of $h$ in the minimum).

There isn't much different between the above description an the pseudocode of the algorithm:

Let A[1],...,A[n] be the elements of the input array.
Let delta be a (n+1)x(k+1) matrix of integers, whose entries are indexed from 0 and initialized with -1 (representing +infinity);

for j=0,...,k:
    delta[0][j]=0;

for i=1,...,n:
    for j=1,...,k:
        for h=i,i-1,...,1:
            if A[i] - A[h]>125: break;
            if delta[h-1][j-1]!=-1 and (delta[i][j]==-1 or delta[h-1][j-1] + A[i] - A[h] < delta[i][j]):
                delta[i][j] = delta[h-1][j-1] + A[i] - A[h];

return delta[n][k];

From a quick look at your problem, it seems that it can be solved in $O(nk)$ time using dynamic programming.

Let $[a_1, \dots, a_n]$ be your input array and define $\delta(i,j)$ as the minimum sum of the differences between the first and last element of each segment in an optimal subdivision of $[a_1, \dots, a_i]$ into at most $j$ segments. If no feasible subdivision exists then let $\delta(i,j) = +\infty$.

Then:

$\delta(0,j)=0$ for any $j \ge 0$;
$\delta(i,0)=+\infty$ for $i>0$; and
$\delta(i,j) = \min_{\substack{h = 1, \dots, i \\ a_i - a_h < 125}} \big\{ \delta(h-1, j-1) + a_i - a_h \big\}$, for $i,j>0$ (where the minimum over an empty set is $+\infty$).

The value of the optimal solution is $\delta(n, k)$ and, since computing each $\delta(i,j)$ requires $O(1)$ time, the overall time required is $O(nk)$. The optimal solution can be reconstructed using standard techniques (e.g., by retracing the optimal choices backwards, or by storing -for each $\delta(i,j)$- the optimal value of $h$ in the minimum).

There isn't much different between the above description an the pseudocode of the algorithm:

Let A[1],...,A[n] be the elements of the input array.
Let delta be a (n+1)x(k+1) matrix of integers, whose entries are indexed from 0 and initialized with -1 (representing +infinity);

for j=0,...,k:
    delta[0][j]=0;

for i=1,...,n:
    for j=1,...,k:
        for h=i,i-1,...,1:
            if A[i] - A[h]>=125: break;
            if delta[h-1][j-1]!=-1 and (delta[i][j]==-1 or delta[h-1][j-1] + A[i] - A[h] < delta[i][j]):
                delta[i][j] = delta[h-1][j-1] + A[i] - A[h];

return delta[n][k];

added 57 characters in body

Source Link

edited Mar 14, 2020 at 12:32

Steven

29.6k
2
28
49

From a quick look at your problem, it seems that it can be solved in $O(nk)$ time using dynamic programming.

Let $[a_1, \dots, a_n]$ be your input array and define $\delta(i,j)$ as the minimum sum of the differences between the first and last element of each segment in an optimal subdivision of $[a_1, \dots, a_i]$ into at most $j$ segments. If no feasible subdivision exists then let $\delta(i,j) = +\infty$.

Then:

$\delta(0,0)=0$$\delta(0,j)=0$ for any $j \ge 0$;
$\delta(i,0)=+\infty$ for $i>0$; and
$\delta(i,j) = \min_{\substack{h = 1, \dots, i \\ a_i - a_h < 125}} \big\{ \delta(h-1, j-1) + a_i - a_h \big\}$, for $i,j>0$ (where the minimum over an empty set is $+\infty$).

The value of the optimal solution is $\delta(n, k)$ and, since computing each $\delta(i,j)$ requires $O(1)$ time, the overall time required is $O(nk)$. The optimal solution can be reconstructed using standard techniques (e.g., by retracing the optimal choices backwards, or by storing -for each $\delta(i,j)$- the optimal value of $h$ in the minimum).

There isn't much different between the above description an the pseudocode of the algorithm:

Let A[1],...,A[n] be the elements of the input array.
Let delta be a (n+1)x(k+1) matrix of integers, whose entries are indexed from 0 and initialized with -1;1 (representing +infinity);
delta[0][0]=0;
for j=0,...,k:
    delta[0][j]=0;

for i=1,...,n:
    for j=1,...,k:
        for h=i,i-1,...,1:
            if A[i] - A[h]>125: break;
            if delta[h-1][j-1]!=-1 and (delta[i][j]==-1 or delta[h-1][j-1] + A[i] - A[h] < delta[i][j]):
                delta[i][j] = delta[h-1][j-1] + A[i] - A[h]; 

return delta[n][k];

From a quick look at your problem, it seems that it can be solved in $O(nk)$ time using dynamic programming.

Let $[a_1, \dots, a_n]$ be your input array and define $\delta(i,j)$ as the minimum sum of the differences between the first and last element of each segment in an optimal subdivision of $[a_1, \dots, a_i]$ into at most $j$ segments. If no feasible subdivision exists then let $\delta(i,j) = +\infty$.

Then:

$\delta(0,0)=0$;
$\delta(i,0)=+\infty$ for $i>0$; and
$\delta(i,j) = \min_{\substack{h = 1, \dots, i \\ a_i - a_h < 125}} \big\{ \delta(h-1, j-1) + a_i - a_h \big\}$, for $i,j>0$ (where the minimum over an empty set is $+\infty$).

The value of the optimal solution is $\delta(n, k)$ and, since computing each $\delta(i,j)$ requires $O(1)$ time, the overall time required is $O(nk)$. The optimal solution can be reconstructed using standard techniques (e.g., by retracing the optimal choices backwards, or by storing -for each $\delta(i,j)$- the optimal value of $h$ in the minimum).

There isn't much different between the above description an the pseudocode of the algorithm:

Let A[1],...,A[n] be the elements of the input array.
Let delta be a (n+1)x(k+1) matrix of integers, whose entries are indexed from 0 and initialized with -1;
delta[0][0]=0;
for i=1,...,n:
    for j=1,...,k:
        for h=i,i-1,...,1:
            if A[i] - A[h]>125: break;
            if delta[h-1][j-1]!=-1 and (delta[i][j]==-1 or delta[h-1][j-1] + A[i] - A[h] < delta[i][j]):
                delta[i][j] = delta[h-1][j-1] + A[i] - A[h];
return delta[n][k];

From a quick look at your problem, it seems that it can be solved in $O(nk)$ time using dynamic programming.

Let $[a_1, \dots, a_n]$ be your input array and define $\delta(i,j)$ as the minimum sum of the differences between the first and last element of each segment in an optimal subdivision of $[a_1, \dots, a_i]$ into at most $j$ segments. If no feasible subdivision exists then let $\delta(i,j) = +\infty$.

Then:

$\delta(0,j)=0$ for any $j \ge 0$;
$\delta(i,0)=+\infty$ for $i>0$; and
$\delta(i,j) = \min_{\substack{h = 1, \dots, i \\ a_i - a_h < 125}} \big\{ \delta(h-1, j-1) + a_i - a_h \big\}$, for $i,j>0$ (where the minimum over an empty set is $+\infty$).

The value of the optimal solution is $\delta(n, k)$ and, since computing each $\delta(i,j)$ requires $O(1)$ time, the overall time required is $O(nk)$. The optimal solution can be reconstructed using standard techniques (e.g., by retracing the optimal choices backwards, or by storing -for each $\delta(i,j)$- the optimal value of $h$ in the minimum).

There isn't much different between the above description an the pseudocode of the algorithm:

Let A[1],...,A[n] be the elements of the input array.
Let delta be a (n+1)x(k+1) matrix of integers, whose entries are indexed from 0 and initialized with -1 (representing +infinity);

for j=0,...,k:
    delta[0][j]=0;

for i=1,...,n:
    for j=1,...,k:
        for h=i,i-1,...,1:
            if A[i] - A[h]>125: break;
            if delta[h-1][j-1]!=-1 and (delta[i][j]==-1 or delta[h-1][j-1] + A[i] - A[h] < delta[i][j]):
                delta[i][j] = delta[h-1][j-1] + A[i] - A[h]; 

return delta[n][k];

added 616 characters in body

Source Link

edited Mar 14, 2020 at 12:25

Steven

29.6k
2
28
49

From a quick look at your problem, it seems that it can be solved in $O(nk)$ time using dynamic programming.

Let $[a_1, \dots, a_n]$ be your input array and define $\delta(i,j)$ as the minimum sum of the differences between the first and last element of each segment in an optimal subdivision of $[a_1, \dots, a_i]$ into at most $j$ segments. If no feasible subdivision exists then let $\delta(i,j) = +\infty$.

Then:

$\delta(0,0)=0$;
$\delta(i,0)=+\infty$ for $i>0$; and
$\delta(i,j) = \min_{\substack{h = 1, \dots, i \\ a_i - a_h < 125}} \big\{ \delta(h-1, j-1) + a_i - a_h \big\}$, for $i,j>0$ (where the minimum over an empty set is $+\infty$).

The value of the optimal solution is $\delta(n, k)$ and, since computing each $\delta(i,j)$ requires $O(1)$ time, the overall time required is $O(nk)$. The optimal solution can be reconstructed using standard techniques (e.g., by retracing the optimal choices backwards, or by storing -for each $\delta(i,j)$- the optimal value of $h$ in the minimum).

There isn't much different between the above description an the pseudocode of the algorithm:

Let A[1],...,A[n] be the elements of the input array.
Let delta be a (n+1)x(k+1) matrix of integers, whose entries are indexed from 0 and initialized with -1;
delta[0][0]=0;
for i=1,...,n:
    for j=1,...,k:
        for h=i,i-1,...,1:
            if A[i] - A[h]>125: break;
            if delta[h-1][j-1]!=-1 and (delta[i][j]==-1 or delta[h-1][j-1] + A[i] - A[h] < delta[i][j]):
                delta[i][j] = delta[h-1][j-1] + A[i] - A[h];
return delta[n][k];

From a quick look at your problem, it seems that it can be solved in $O(nk)$ time using dynamic programming.

Let $[a_1, \dots, a_n]$ be your input array and define $\delta(i,j)$ as the minimum sum of the differences between the first and last element of each segment in an optimal subdivision of $[a_1, \dots, a_i]$ into at most $j$ segments. If no feasible subdivision exists then let $\delta(i,j) = +\infty$.

Then:

$\delta(0,0)=0$;
$\delta(i,0)=+\infty$ for $i>0$; and
$\delta(i,j) = \min_{\substack{h = 1, \dots, i \\ a_i - a_h < 125}} \big\{ \delta(h-1, j-1) + a_i - a_h \big\}$, for $i,j>0$ (where the minimum over an empty set is $+\infty$).

The value of the optimal solution is $\delta(n, k)$ and, since computing each $\delta(i,j)$ requires $O(1)$ time, the overall time required is $O(nk)$. The optimal solution can be reconstructed using standard techniques (e.g., by retracing the optimal choices backwards, or by storing -for each $\delta(i,j)$- the optimal value of $h$ in the minimum).

From a quick look at your problem, it seems that it can be solved in $O(nk)$ time using dynamic programming.

Let $[a_1, \dots, a_n]$ be your input array and define $\delta(i,j)$ as the minimum sum of the differences between the first and last element of each segment in an optimal subdivision of $[a_1, \dots, a_i]$ into at most $j$ segments. If no feasible subdivision exists then let $\delta(i,j) = +\infty$.

Then:

$\delta(0,0)=0$;
$\delta(i,0)=+\infty$ for $i>0$; and
$\delta(i,j) = \min_{\substack{h = 1, \dots, i \\ a_i - a_h < 125}} \big\{ \delta(h-1, j-1) + a_i - a_h \big\}$, for $i,j>0$ (where the minimum over an empty set is $+\infty$).

The value of the optimal solution is $\delta(n, k)$ and, since computing each $\delta(i,j)$ requires $O(1)$ time, the overall time required is $O(nk)$. The optimal solution can be reconstructed using standard techniques (e.g., by retracing the optimal choices backwards, or by storing -for each $\delta(i,j)$- the optimal value of $h$ in the minimum).

There isn't much different between the above description an the pseudocode of the algorithm:

Let A[1],...,A[n] be the elements of the input array.
Let delta be a (n+1)x(k+1) matrix of integers, whose entries are indexed from 0 and initialized with -1;
delta[0][0]=0;
for i=1,...,n:
    for j=1,...,k:
        for h=i,i-1,...,1:
            if A[i] - A[h]>125: break;
            if delta[h-1][j-1]!=-1 and (delta[i][j]==-1 or delta[h-1][j-1] + A[i] - A[h] < delta[i][j]):
                delta[i][j] = delta[h-1][j-1] + A[i] - A[h];
return delta[n][k];

deleted 3 characters in body

Source Link

edited Mar 11, 2020 at 15:10

Steven

29.6k
2
28
49

Loading

edited body

Source Link

edited Mar 11, 2020 at 15:01

Steven

29.6k
2
28
49

Loading

Source Link

created Mar 11, 2020 at 14:55

Steven

29.6k
2
28
49

Loading

Stack Exchange Network

Return to Answer