题目描述

给你一个由 正 整数组成的数组 nums 。

如果 nums 的子数组中位于 不同 位置的每对元素按位 与（AND）运算的结果等于 0 ，则称该子数组为 优雅 子数组。

返回 最长 的优雅子数组的长度。

子数组 是数组中的一个 连续 部分。

注意：长度为 1 的子数组始终视作优雅子数组。

示例 1：

输入：nums = [1,3,8,48,10] 输出：3 解释：最长的优雅子数组是 [3,8,48] 。子数组满足题目条件：

3 AND 8 = 0 3 AND 48 = 0 8 AND 48 = 0 可以证明不存在更长的优雅子数组，所以返回 3 。

示例 2：

输入：nums = [3,1,5,11,13] 输出：1 解释：最长的优雅子数组长度为 1 ，任何长度为 1 的子数组都满足题目条件。

提示：

1 <= nums.length <= 105 1 <= nums[i] <= 109

coding

class Solution {
          
   
    public int longestNiceSubarray(int[] nums) {
          
   
        int res = 1;
        // 存储当前位置为最终索引的子序列长度
        int[] dp = new int[nums.length];
        Arrays.fill(dp, 1);
        for (int i = 1; i < nums.length; i ++) {
          
   
            dp[i] = dp[i - 1] + 1;

            // 必须逆序遍历, 否则 i 处的最大子序列是有问题的, 不可以直接默认 1 (存小了...)
            // for (int j = i - dp[i - 1]; j < i ; j ++) {
          
   
            //     if ((nums[i] & nums[j]) != 0) {
          
   
            //         dp[i] = 1;
            //         break;
            //     }
            // }
            for (int j = i - 1; j >= i - dp[i - 1]; j --) {
          
   
                if ((nums[i] & nums[j]) != 0) {
          
   
                    dp[i] = i - j;
                    break;
                }
            }
            res = Math.max(res, dp[i]);
        }
        return res;
    }
}