连续子数组_所有连续子数组

给定一个元素为0或1的数组nums，一个非负整数n表示最多有n次机会，将指定位置的0变为1或者1变为0。试问，经过最多n次转换后，最长的连续为1或0的子数组的长度。

动态规划：假定先考虑，将0转为1，求最长的连续为1的子数组。
dp[i][j]表示第i次转换，以j为结尾的最长的子数组的长度。
dp[i][j]=dp[i-1][j-1]+1,nums[j]==0;
dp[i][j]=dp[i][j-1]+1,nums[j]==1。

	public int getMaxConsecutiveOnes (int[] arr, int n) {
        return Math.max(func(arr,n,1),func(arr,n,0));
    }
    private int func(int[] arr, int n,int bit) {
        // write code here
        int len=arr.length;
        int[][] dp=new int[n+1][len+1];
        for(int i=0;i<len;i++){
            if(arr[i]==bit){
                dp[0][i+1]=dp[0][i]+1;
            }
        }
        for(int i=1;i<=n;i++){
            for(int j=1;j<=len;j++){
                if(arr[j-1]==(1-bit)){
                    dp[i][j]=dp[i-1][j-1]+1;
                }else{
                    dp[i][j]=dp[i][j-1]+1;
                }
            }
        }
        int ret=0;
        for(int j=1;j<=len;j++){
            ret=Math.max(ret,dp[n][j]);
        }
        return ret;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27