G - 小彬的周赛（easy）

SDUT OnlineJudge

Description

在一场朴实无华的LeetCode周赛中，小彬正在苦思冥想一道题目，然而满屏的wrong answer让小彬陷入深思……

“淦，原来读错题了。”

这道题目原本的描述是这个样子的：

小彬把题目中的组合读成了子数组的含义。当他发现问题后很快AC了这道题目。

但是现在小彬希望解决读错后的题目，你能帮助他解决问题吗？

Input

第一行一个正整数 nn ，代表数组长度。（1 \leq n \leq 10^51≤n≤105）

第二行 nn 个正整数，表示数组 nums 。（1 \leq nums[i] < 2^{30}1≤nums[i]<230）

Output

输出一个整数，表示按位与结果大于 00 的最长子数组的长度。

Sample

Input 

3
1 5 3

Output 

3

Hint

按位与：如 77 的二进制形式为 01110111 ，1313 的二进制形式为 11011101 ，那么 77 & 1313 = 01010101 = 55 。

子数组：数组中连续的一个或多个元素组成的数组。

组合：数组中的若干个元素组成的数组（不要求连续）。

#include
using namespace std;
int a[100010];
int main()
{
    int n,ans=0;
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&a[i]);
    }
    for(int i=1;i<=n;i++)
    {
        int j;
        int m=a[i];
        for(j=i+1;j<=n;j++)
        {
            if(m&a[j])
               m=m&a[j];
            else
                break;
        }
        ans=max(ans,j-i);
        if(ans>=n-i+1)break;//如果ans>=n-i+1,那么后面就算有结果大于零的组合，也没有ans大
    }
    printf("%d",ans);
}

当时比赛没做出来，因为这题跟以前做的dp有点像，其实暴力枚举就行