Sponsored
Sponsored
This approach involves finding the maximum element in the array since it would potentially be the maximum bitwise AND when considered individually or consecutively. Then, we scan through the array to find the longest subarray containing only this element.
Time Complexity: O(n) because we iterate through the array once.
Space Complexity: O(1) as no extra space is used apart from variables.
1def longest_max_and_subarray(nums):
2 max_element = 0
3 current_length = 0
4 longest_length = 0
5 for num in nums:
6 if num > max_element:
7 max_element = num
8 current_length = 1
9 longest_length = 1
10 elif num == max_element:
11 current_length += 1
12 longest_length = max(longest_length, current_length)
13 else:
14 current_length = 0
15 return longest_length
16
17nums = [1, 2, 3, 3, 2, 2]
18print(longest_max_and_subarray(nums))This Python function utilizes a similar logic to find the longest subarray having the maximum element.
This approach involves using a sliding window to determine the longest subarray where the bitwise AND remains at its maximum value. Begin from the end of the array since the maximum AND value after considering all elements is often the last element itself or a combination found traversing backward.
Time Complexity: O(n), as it involves a single backward traversal.
Space Complexity: O(1).
Initially, the maximum AND is assumed to be the last element. A reverse scan utilizing a sliding window calculates the longest subarray conforming to this value.