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.
1#include <stdio.h>
2
3int longestMaxAndSubarray(int* nums, int numsSize) {
4 int maxElement = 0, currentLength = 0, longestLength = 0;
5 for (int i = 0; i < numsSize; i++) {
6 if (nums[i] > maxElement) {
7 maxElement = nums[i];
8 currentLength = 1;
9 longestLength = 1;
10 } else if (nums[i] == maxElement) {
11 currentLength++;
12 if (currentLength > longestLength) {
13 longestLength = currentLength;
14 }
15 } else {
16 currentLength = 0;
17 }
18 }
19 return longestLength;
20}
21
22int main() {
23 int nums[] = {1, 2, 3, 3, 2, 2};
24 int numsSize = sizeof(nums) / sizeof(nums[0]);
25 printf("%d\n", longestMaxAndSubarray(nums, numsSize));
26 return 0;
27}The code finds the maximum element in the array and then iterates through the array to find the longest contiguous subarray of this maximum element. If a new maximum element is found, it resets the count.
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).
1
public class Solution {
public int LongestSubarray(int[] nums) {
int maxAnd = nums[nums.Length - 1];
int longest = 0, count = 0;
for (int i = nums.Length - 1; i >= 0; i--) {
if ((maxAnd & nums[i]) == maxAnd) {
count++;
longest = Math.Max(longest, count);
} else {
count = 0;
}
}
return longest;
}
public static void Main() {
Solution sol = new Solution();
int[] nums = {1, 2, 3, 3, 2, 2};
Console.WriteLine(sol.LongestSubarray(nums));
}
}C# approach, assuming end element as maximum AND, traverses backward to compute maximum subarray length with valid AND.