Suren
BAN USERHere is the best/optimum solution through dynamic-programming...
Assume Given
N=8
A[0...7] = {1,0,0,1,0,0,1,0}
int Zeros (int A[], int i, int j) {
int countZeros = 0;
if (i < j) {
for (int k = i, k < j; ++k) {
if (!A[k]) {
countZeros++;
}
}
}
return countZeros;
}
int R[N-1][N-1] = {-1};
int flip (int A[], int R[][], int i, int j) {
if (i < j) {
if (R[i][j] != -1) {
return R[i][j];
} else {
R[i][j] = max{ Zeros(A, i, j),
1&A[i] + flip(A, R, i+1, j),
flip(A, R, i, j-1) + 1&A[j],
1& A[i] + flip(A, R, i+1, j-1) + 1&A[j]
};
}
} else if (i == j){
return !A[i];
} else {
return 0;
}
return R[i][j];
}
int main () {
printf("Max Number of 1s: ", flip (A, R, 0, N-1));
}
Following is bruit-force cum semi-dynamic solution. R[N-1][N-1] matrix stores the number of 1s for each iteration. The stored R matrix can be used in computation to optimize the solution via dynamic-programming.
Assume Given
N=8
A[0...7] = {1,0,0,1,0,0,1,0}
R[N-1][N-1] = {0};
for (int i = 0; i < N-1; ++i) {
for (int j = N-1; j > i; --j) {
int k = i;
while (k < j) {
if (!A[k]) {
R[i][j]++;
}
}
}
}
return max{R[i][j]; where 0 < i < N-1 and 0 < j < N-1}
Following is bruit-force cum semi-dynamic solution. R[N-1][N-1] matrix stores the number of 1s for each iteration. The stored R matrix can be used in computation to optimize the solution via dynamic-programming.
Assume Given
N=8
A[0...7] = {1,0,0,1,0,0,1,0}
R[N-1][N-1] = {0};
for (int i = 0; i < N-1; ++i) {
for (int j = N-1; j > i; --j) {
int k = i;
while (k < j) {
if (!A[k]) {
R[i][j]++;
}
}
}
}
In above code, replace call to function f() by flip().
- Suren September 21, 2014