package main;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

/**
 * 我們有一個(gè)非負(fù)整數(shù)數(shù)組 A从橘。
 *
 * 對(duì)于每個(gè)（連續(xù)的）子數(shù)組 B = [A[i], A[i+1], ..., A[j]] （ i <= j）锅知，我們對(duì) B 中的每個(gè)元素進(jìn)行按位或操作誉察，獲得結(jié)果 A[i] | A[i+1] | ... | A[j]很魂。
 *
 * 返回可能結(jié)果的數(shù)量。 （多次出現(xiàn)的結(jié)果在最終答案中僅計(jì)算一次。）
 *
 *  
 *
 * 示例 1：
 *
 * 輸入：[0]
 * 輸出：1
 * 解釋：
 * 只有一個(gè)可能的結(jié)果 0 。
 * 示例 2：
 *
 * 輸入：[1,1,2]
 * 輸出：3
 * 解釋：
 * 可能的子數(shù)組為 [1]绳锅，[1]，[2]酝掩，[1, 1]鳞芙，[1, 2]，[1, 1, 2]。
 * 產(chǎn)生的結(jié)果為 1积蜻，1闯割，2，1竿拆，3，3 宾尚。
 * 有三個(gè)唯一值丙笋，所以答案是 3 。
 * 示例 3：
 *
 * 輸入：[1,2,4]
 * 輸出：6
 * 解釋：
 * 可能的結(jié)果是 1煌贴，2御板，3，4牛郑，6怠肋，以及 7 。
 *  
 *
 * 提示：
 *
 * 1 <= A.length <= 50000
 * 0 <= A[i] <= 10^9
 *
 * 來(lái)源：力扣（LeetCode）
 * 鏈接：https://leetcode-cn.com/problems/bitwise-ors-of-subarrays
 * 著作權(quán)歸領(lǐng)扣網(wǎng)絡(luò)所有淹朋。商業(yè)轉(zhuǎn)載請(qǐng)聯(lián)系官方授權(quán)笙各，非商業(yè)轉(zhuǎn)載請(qǐng)注明出處。
 */
public class BitwiseOrsOfSubarrays {

  public static void main(String[] args) {
    int[] param = new int[]{1,2,3,4};
    System.out.println("可能的結(jié)果數(shù)為："+subarrayBitwiseORs(param));
  }

/*
 *參考如下作者
 *作者：hundanLi
 *鏈接：https://leetcode-cn.com/problems/bitwise-ors-of-subarrays/solution/dong-tai-gui-hua-by-hundanli-4/
 *來(lái)源：力扣（LeetCode）
 *著作權(quán)歸作者所有础芍。商業(yè)轉(zhuǎn)載請(qǐng)聯(lián)系作者獲得授權(quán)杈抢，非商業(yè)轉(zhuǎn)載請(qǐng)注明出處。
*/
  public static int subarrayBitwiseORs(int[] arr) {
    //重點(diǎn)在于如何將連續(xù)的組合或數(shù)據(jù)存儲(chǔ)起來(lái)
    Set<Integer> set = new HashSet<>();
    for (int i = 0; i < arr.length; i++) {
      set.add(arr[i]);
      for (int j = i - 1; j >= 0; j--) {
        if ((arr[i] | arr[j]) == arr[j]) {
          // arr[j]的置位位置包含了arr[i]的置位位置仑性，
          // 那么已經(jīng)無(wú)需考慮arr[i]的加入與否
          break;
        }
        // 求值的同時(shí)保留積累狀態(tài)
        arr[j] |= arr[i];
        set.add(arr[j]);
      }
    }
    return set.size();
  }
}