第11天，今天刷的是一道动态规划的题目。

今天的题目是Bitwise ORs of Subarrays:

这道题的时间复杂度很高，我们用个例子来解释解法：

首先输入是[1, 2, 4],我们先看下能不能用[1, 2]的答案来推出[1, 2, 4]的答案：

[1, 2]的答案是1, 2, 3如果都与4或一下的话，会得到的是[5, 6, 7]，而[1, 2, 4]的答案中应该是没有5的，那么问题出在哪里了呢？如果仔细想一下的话，会发现这里要求的是连续子数组，而以4为结尾的连续子数组只有：[4], [2, 4], [1, 2, 4]，对它们进行或也就是说其实1其实是不会和4进行或运算的。

那么要和4进行或运算的数组是什么呢？答案是一个空数组和所有以2结尾的连续子数组的或运算结果，而进行完或运算后得到的结果就是所有以4结尾的或运算结果。

这时候我们就很容易想到解法了：

用一个set保存所有以A[i-1]结尾的或运算结果，记为set[i-1]，然后分别与A[i]进行或运算插入到另一个set中，并在最后插入一个A[i]就可以得到set[i]。

故：

1
class Solution {
2
public:
3
    int subarrayBitwiseORs(vector<int>& A) {
4
        int len = A.size();
5
        if (len == 0) return 0;
6

7
        unordered_set<int> res, cur, cur2;
8
        for(auto &i: A) {
9
            cur2 = {i};
10
            for(auto &j : cur) cur2.insert(i | j);
11
            cur = cur2;
12
            for(auto &j: cur) res.insert(j);
13
        }
14
        return res.size();
15
    }
1 collapsed line
16
};