http://churmura.com/algorithms/vmware-online-coding-test-for-us-recruitments-hyderabad-event/69549/

/* Copyleft: Ming Lin <minggr@gmail.com> */ #include <stdio.h> int count[100][100]; int flip_bits(int data[], int n) { int len, i, j; int max = -1; int bits = 0; for (i = 0; i < n; i++) if (data[i] == 1) bits++; for (len = 1; len <= n; len++) { for (i = 0; i <= n-len; i++) { j = i+len-1; if (len == 1) { if (data[j] == 0) count[i][j] = bits + 1; else count[i][j] = bits - 1; } else { if (data[j] == 0) count[i][j] = count[i][j-1] + 1; else count[i][j] = count[i][j-1] - 1; } //printf("count[%d][%d]: %d\n", i, j, count[i][j]); if (max == -1 || count[i][j] > max) max = count[i][j]; } } return max; } int main() { int data[] = {1, 0, 0, 1, 0, 0, 1, 0}; int n = 8; printf("%d\n", flip_bits(data, n)); return 0; }