个人练习-Leetcode-898. Bitwise ORs of Subarrays

题目链接：https://leetcode.cn/problems/bitwise-ors-of-subarrays/

题目大意：给出一个数列arr[]，求【所有可能子列的】【所有元素做位运算或】的结果的个数。

思路：刚开始按子列的开始位置和子列长度遍历，len+1长度的子列的结果可以由len长度的子列和一个元素做位运算得到。原以为这样子节约了时间，后来想想好像还是把所有结果都算了一遍，时间过不了。

看了题解，注意到或|的位运算只会让非负整数【增大】，那么实际上最大的可能值就是arr[]所由元素做或运算。由于题目中arr[i] <= 1e9，那么上限实际上是可以确定的。在遍历时，如果某个子列已经达到上限，直接剪枝。

完整代码

class Solution {
public:int subarrayBitwiseORs(vector<int>& arr) {int N = arr.size();set<int> res;int MAXE = 0;for (int i = 0; i < N; i++)MAXE |= arr[i];for (int i = 0; i < N; i++) {int now = arr[i];res.insert(now);for (int j = i+1; j < N; j++) {now |= arr[j];res.insert(now);if (now == MAXE)break;}}return res.size();}   
};