【动态规划】按位与最大的最长子数组

最大连续子数组和+求对应的最大长度。

6189. 按位与最大的最长子数组、

给你一个长度为 n 的整数数组 nums 。

考虑 nums 中进行 按位与（bitwise AND）运算得到的值 最大 的 非空 子数组。

• 换句话说，令 k 是 nums 任意 子数组执行按位与运算所能得到的最大值。那么，只需要考虑那些执行一次按位与运算后等于 k 的子数组。

返回满足要求的 最长 子数组的长度。

数组的按位与就是对数组中的所有数字进行按位与运算。

子数组 是数组中的一个连续元素序列。

思路：

dp[i]以nums[i]结尾的运算的最大值

start[i]表示以nums[i]结尾的最大值的开始位置

当dp[i-1]与nums[i]大于等于(因为要求最大长度,所以要取等号)dp[i]时,start[i]=start[i-1]

当dp[i-1]与nums[i]小于dp[i]时,start[i]=i

找出最大值,然后找出最大值的长度:max(i-start[i]+1),其中dp[i]是最大值

class Solution {
    public int longestSubarray(int[] nums) {
         int[]dp=new int[nums.length];
         int[]start=new int[nums.length];
         for(int i=0;i
             dp[i]=nums[i];
         }
         dp[0]=nums[0];
         start[0]=0;
         int m=dp[0];
         int len=1;
         for(int i=1;i
             if((dp[i-1]&nums[i])>=dp[i]){
                 start[i]=start[i-1];
                 dp[i]=dp[i-1]&nums[i];
             }else{
                 start[i]=i;
             }
             m=Math.max(m,dp[i]);
         }
        int res=1;
        for(int i=0;i
            if(dp[i]==m)res=Math.max(res,i-start[i]+1);
        }
        return res;
         
        
    
        
    }
}