我们有一个如下的位数组
{1 0 1 0 0 1 0 1}
以上数组中的位数为8
如果我们从[1,5]取范围，则[1,5] 范围内的位数为[0 1 0 0 1]。
如果我们翻转这个范围，那么翻转后它将变成[ 1 0 1 1 0]
因此，在翻转[1,5]范围后的1的总数是[1 1 0 1 1 0 0 1] = 5
如果我们从[1,6]取范围，则[1,6] 范围内的位数为[0 1 0 0 1 0]。
如果我们翻转这个范围，那么翻转后它将变成[ 1 0 1 1 0 1]
因此，在翻转[1,5]范围后的1的总数是[1 1 0 1 1 0 1 1] = 6
因此，答案是范围为[1,6]，在翻转后我们可以在数组中得到6个1
是否有一个好的算法可以解决这个问题。我只能想到动态规划，因为这个问题可以分解成子问题，然后将它们组合起来。
受@Nabbs评论的启发，有一种简单的方法可以在线性时间内解决这个问题：将问题转化为最大段和。
将所有的0变成1，所有的1变成-1。问题就变成了在变换后的数组中最小化数组的和。（变换后的最小和包含了变换后的数组中大多数的-1，对应原问题中的大多数1）
我们可以计算总和：
sum(after flipping) = sum(non-flipped) - sum(flipped part before flipping)
因为翻转部分的和被倒置了。现在，如果我们将未翻转部分表示如下：
sum(non-flipped) = sum(original array) - sum(flipped part before flipping)
我们发现需要将其最小化。
sum(after flipping) = sum(original array) - 2 sum(flipped part before flipping)
第一部分是一个常数，因此我们需要真正最大化翻转部分的总和。这正是最大连续子段和问题所做的。
我曾经写了一个冗长的推导来解决这个问题，时间复杂度为线性 一段时间前，所以现在我只分享代码。下面我更新了代码，以便还能存储边界。我选择 JavaScript 作为语言，因为它在浏览器中非常易于测试，而且我不必显式地声明变量 x 和 y 的类型。
var A = Array(1, 0, 1, 0, 0, 1, 0, 1);
var sum = 0;
// count the 1s in the original array and
// do the 0 -> 1 and 1 -> -1 conversion
for(var i = 0; i < A.length; i++) {
sum += A[i];
A[i] = A[i] == 0 ? 1 : -1;
}
// find the maximum subarray
var x = { value: 0, left: 0, right: 0 };
var y = { value: 0, left: 0 };
for (var n = 0; n < A.length; n++) {
// update y
if (y.value + A[n] >= 0) {
y.value += A[n];
} else {
y.left = n+1;
y.value = 0;
}
// update x
if (x.value < y.value) {
x.left = y.left;
x.right = n;
x.value = y.value;
}
}
// convert the result back
alert("result = " + (sum + x.value)
+ " in range [" + x.left + ", " + x.right + "]");
result = 6 in range [1, 4]
#include <iostream>
#include <bitset>
#include <utility>
typedef std::pair<unsigned, unsigned> range_t;
template <std::size_t N>
range_t max_flip(const std::bitset<N>& bs){
int overall_score = 0;
range_t result = range_t{0,0};
for(std::size_t i = 0; i < N; ++i){
int score = bs[i] ? -1 : 1;
auto max = i;
for(std::size_t j = i + 1; j < N; ++j){
auto new_score = score + (bs[j] ? -1 : 1);
if(new_score > score){
score = new_score;
max = j;
}
}
if(score > overall_score){
overall_score = score;
result = {i,max};
}
}
return result;
}
int main(){
std::bitset<8> bitfield(std::string("10100101"));
range_t range = max_flip(bitfield);
std::cout << range.first << " .. " << range.second << std::endl;
}
-std=C++0x正常工作。您需要符合C++03标准的版本吗？ - Zeta在O(n)中进行第二次尝试
从数组的开头开始。遍历整个数组，在遇到0之前一直向前移动。当您遇到第一个0时，将计数器设置为0，记住起始位置并继续向前移动同时计数：+1表示0，-1表示1。如果计数器变为负数，则重置计数器并继续移动，直到到达末尾。如果您找到另一个零，则将计数器设置为0并重复上一个算法。最后，如果有必要，翻转起始和结束位置的范围。
void Flip( int* arr , int len )
{
int s = -1 , e = -1 , c ;
for( int i = 0 ; i < len ; i++ )
{
if( arr[i] == 0 )
{
c = 0 ;
s = i ;
e = i ;
for( int j = i ; j < len ; j++ , i++ )
{
if( arr[i] == 0 )
c++ ;
else
c-- ;
if( c < 0 )
{
s = -1 ;
e = -1 ;
break ;
}
if( arr[i] == 0 )
e = i ;
}
}
}
if( s > -1 )
for( int i = s ; i <= e ; i++ )
arr[i] ^= 1 ;
for( int i = 0 ; i < len ; i++ )
printf("%d " , arr[i] ) ;
}
int main(void)
{
int a[13] = {1,0,1,1,0,0,1,0,1,1,0,1,0} ;
Flip( a , 13 ) ;
return 0;
}
没有进行彻底测试，可能存在一些漏洞(边缘情况)，但原则上可以工作。
public static void main(String[] args) {
int [] input = {1, 0, 0, 1, 0, 0, 1,1,1,1, 0,1};
System.out.println(findMaxNumberOfOnes(input,0, input.length-1));
}
private static int findMaxNumberOfOnes(int[] input, int i, int j) {
if (i==j)
return 1;
int option1 = input[i] + findMaxNumberOfOnes(input, i+1, j);
int option2 = count(input , i , j, true);
int option3 = count(input, i, j, false);
int option4 =findMaxNumberOfOnes(input, i, j-1) +input[j];
return Math.max(option1, Math.max(option2,Math.max(option3,option4)));
}
private static int count(int[] input, int i, int j, boolean flipped) {
int a = flipped?0:1;
int count = 0;
while (i<=j){
count += (input[i++]==a)?1:0;
}
return count;
}
我也和@this一样这么想。但是他的解决方案中有些bug。我修复了这个bug后的代码（见下面的解释）：
vector<int> Solution::flip(string arr) {
int s = -1 , e = -1 , c , len = arr.size(), S = -1, E = -1, Max = 0;
for( int i = 0 ; i < len ; i++ )
{
if( arr[i] == '0' )
{
c = 0 ;
s = i ;
e = i ;
for( int j = i ; j < len ; j++, i++ )
{
if( arr[j] == '0' )
c++ ;
else
c-- ;
//cout << c << " ";
if( c < 0 )
{
s = -1 ;
e = -1 ;
break ;
}
if( arr[j] == '0' )
e = i ;
if(c > Max){
S = s;
E = e;
Max = c;
}
}
}
}
vector<int> ans;
if( S > -1 ){
ans.push_back(S);
ans.push_back(E);
return ans;
}
else
return ans;
}
解释： 从数组的开头开始。遍历整个数组，直到找到一个0。当你找到第一个0时，将计数器设置为0，记住起始位置，并继续向前移动，同时进行计数：对于0加1，对于1减1。Max存储所有集合[s, e]中最大数量的0的值。如果c大于Max，则当前集合[s, e]包含最多的'0'位数。因此更新Max, S, E,。如果计数变为负数，则意味着在集合[s, e]中'1'的数量大于'0'的数量，因此重置计数器c，本地起始位置s，本地结束位置e，并继续直到达到末尾。如果您找到另一个零，则将计数器设置为0并重复上一个算法。最终的S，E的值是要翻转位的范围的索引。如果不存在这样的范围（所有位都是'1'），则S = -1, E = - 1。这个问题可以使用动态规划在线性时间和空间内解决。您可以创建一个名为 left 的数组，其中 left[i] 是子数组 0 到 i（包括 i）上 1 的数量。因此，对于两个索引 i 和 j：
case 1: i==j, result is array size sz-1 (if no 0 in array) or sz+1 (if there is at least one 0 in array)
case 2: i less than j, result is:
left[i-1] (# of 1 on subarray 0 ~ i-1) +
(j-i+1-(left[j]-left[i-1])) (# of 0 on subarray i ~ j) +
left[sz-1]-left[j] (# of 1 on subarray j+1 ~ sz-1)
this equals to: (j-2*left[j])-(i-2*left[i-1])+left[sz-1]+1
所以根据第二种情况，我们需要另一个数组 temp 来存储每个 j 的 min{i-2*left[i-1] where i<j}
因此，我们可以遍历数组，在每个索引 j 处计算上述情况二（在常数时间内），并更新最终结果，如果它更大。
我的 C++ 代码：
int func(vector<int>& arr){
int res = 0;
int sz = arr.size();
vector<int> left(sz, 0);
for(int i=0; i<sz; i++){
left[i] = (arr[i]==1?1:0)+(i==0?0:left[i-1]);
}
bool all_1 = true;
for(int i=0; i<sz; i++){
if(arr[i] == 0) all_1=false;
}
if(all_1) return sz-1;
res = left[sz-1]+1;
vector<int> temp(sz, INT_MAX);
for(int i=1; i<sz; i++)
temp[i] = min(temp[i-1], i-2*left[i-1]);
for(int j=1; j<sz; j++){
int val = j+1-left[j]+(left[sz-1]-left[j]);
val = max(val, j-2*left[j]-temp[j]+left[sz-1]+1);
res = max(res, val);
}
return res;
}
让我提供解决方案，它实际上是基于Kadane算法。
代码有点长，但大部分都是我写的注释，以帮助您更好地理解。
空间复杂度：O(1) 时间复杂度：O(n)
# flip to zero to get max one
def flip_zero(nums):
# max number of 0 at index and global
max_nums_at_index, max_nums_global = None, None
start, end = None, None
for i in range(len(nums)):
if i == 0:
if nums[i] == 0:
# In position 0, if the digit is 0, then the count of zero will be 1
max_nums_at_index, max_nums_global = 1, 1
else:
# In position 0, if the digit is 1, then the count of zero will be 0
max_nums_at_index, max_nums_global = 0, 0
# Mark the start and end position of the substring
start, end = i, i
else:
# In other position, we need to consider we are going to added it or not
if nums[i] == 0:
# If the number is 0, then after we included it the count of zero will be increased by 1
# If we don't add it and means we will start a new subarray from current index
# the count of zero at current index will be 1
# So here we need to do comparison and see which one is bigger.
max_nums_at_index = max(max_nums_at_index + 1, 1)
# Check whether we start a new sub array, if yes, update the start index
if max_nums_at_index == 1:
start = i
else:
# If the number is 1, then after we include it the count of zero will remain unchange
# If we don't add it and means we will start a new array from current index
# the count of zero at current index will be 0
# So here we need to do comparison and see which one is bigger.
max_nums_at_index = max(max_nums_at_index, 0)
# Check whether we start a new sub array, if yes, update the start index
if max_nums_at_index == 0:
start = i
temp = max_nums_global
max_nums_global = max(max_nums_global, max_nums_at_index)
# Check whether the global max has been updated, if yes, update the end index
if max_nums_global != temp:
end = i
return [start, end]
返回的结果是 [1, 6]
这个也可以更加简单。看看这个Python示例O(n)：
def flipBits_for_maximum_1s (a, n):
countOfOnes = 0
# find contiguous subarray with biggest sum
# of 'count of 0s' - 'count of 1s'
big = cur_big = 0
for x in a:
if x:
countOfOnes += 1
cur_big -= 1
else: cur_big += 1
if cur_big > big: big = cur_big
if (cur_big < 0): cur_big = 0;
return big + countOfOnes
这个解决方案也受到了@Nabb评论的启发。我创建了一个新数组，将0替换为1，将1替换为-1。然后我使用最大子数组和范围问题的概念来解决它。代码如下：
vector<int> Solution::flip(string A) {
vector<int> vec;
vector<int> res;
for(int i=0;i<A.length();i++){
if(A[i]=='1')
vec.push_back(-1);
else
vec.push_back(1);
}
int l=0,r=0,s=0;
int sum=0;
int sum_prev=INT_MIN;
for(int i=0;i<vec.size();i++){
sum+=vec[i];
if(sum_prev<sum){
sum_prev=sum;
l=s;
r=i;
}
if(sum<0){
sum=0;
s=i+1;
}
}
//cout<<"l: "<<l<<" r: "<<r<<endl;
if((l>=0 && r>0)||((l==0 && r==0) && A[0]=='0')){
res.push_back(l+1);
res.push_back(r+1);
}
return res;
}