You are given an integer array `nums`

of size `n`

.

Consider a **non-empty** subarray from `nums`

that has the **maximum** possible **bitwise AND**.

- In other words, let
`k`

be the maximum value of the bitwise AND of**any**subarray of`nums`

. Then, only subarrays with a bitwise AND equal to`k`

should be considered.

Return *the length of the longest such subarray*.

The bitwise AND of an array is the bitwise AND of all the numbers in it.

A **subarray** is a contiguous sequence of elements within an array.

**Example 1:**

Input:nums = [1,2,3,3,2,2]Output:2Explanation:The maximum possible bitwise AND of a subarray is 3. The longest subarray with that value is [3,3], so we return 2.

**Example 2:**

Input:nums = [1,2,3,4]Output:1Explanation:The maximum possible bitwise AND of a subarray is 4. The longest subarray with that value is [4], so we return 1.

**Constraints:**

`1 <= nums.length <= 10`

^{5}`1 <= nums[i] <= 10`

^{6}

**Solution: Find the largest number**

a & b <= a

a & b <= b

if b > a, a & b < b, we choose to start a new sequence of “b” instead of continuing with “ab”

Basically, we find the largest number in the array and count the longest sequence of it. Note, there will be some tricky cases like.

b b b b a b

b a b b b b

We need to return 4 instead of 1.

Time complexity: O(n)

Space complexity: O(1)

## C++

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 |
// Author: Huahua class Solution { public: int longestSubarray(vector<int>& nums) { int ans = 0; int best = 0; for (int i = 0, l = 0; i < nums.size(); ++i) { if (nums[i] > best) { best = nums[i]; ans = l = 1; } else if (nums[i] == best) { ans = max(ans, ++l); } else { l = 0; } } return ans; } }; |