题意

给 n 个非负整数，请你求出最大或和，最小或和，最大与和，最小与和这四个数之和。

样例

给出 n = 3, nums = [1, 2, 3]，返回 7。

解释：
最大或和：3，最小或和：1，最大与和：3，最小与和：0。

答案：3 + 1 + 3 + 0 = 7。
给出 n = 3, nums = [0, 0, 1]，返回 2。

解释：
最大或和：1，最小或和：0，最大与和：1，最小与和：0。

答案：1 + 0 + 1 + 0 = 2。
给出 n = 5, nums = [12313, 156, 4564, 212, 12]，返回25090。

解释：
最大或和：12765，最小或和：12，最大与和：12313，最小与和：0。

答案：12765 + 12 + 12313 = 25090。
给出 n = 3, nums = [111111, 333333, 555555]，返回 1588322。

解释：

最大或和：917047，最小或和：111111，最大与和：555555，最小与和：4609。

答案：917047+ 111111+ 555555+ 4609 = 1588322。

注意事项

最大或和为在 n 个数中，任取若干个数（不能不取），进行或运算后最大的数。
最小或和为在 n 个数中，任取若干个数（不能不取），进行或运算后最小的数。
最大与和为在 n 个数中，任取若干个数（不能不取），进行与运算后最大的数。
最小与和为在 n 个数中，任取若干个数（不能不取），进行与运算后最小的数。
1 <= n <= 1000000，0 <= nums[i] <= 2^32 - 1。

1.解题思路

  本来这个题，我第一个想法就是使用回溯法，来遍历每种情况的结果，然后在从中选出想要的结果就行了。果然，出乎意料的超时！当时就在想，既然回溯能做这个题，那么动态规划的应当也可以。
  首先，我们定义一个dp数组，dp[i]表示第个数的最大或和。而这个或和，要么是dp[i - 1],要么是dp[i - 1]和nums[i]的或值。然后反复的和dp[i]取最大值就行了。至于三个值的也是如此这样求解出来的

2.代码

    public long getSum(int n, int[] nums) {

        int res[][] = new int[4][n];
        for (int i = 0; i < nums.length; i++) {
            res[0][i] = nums[i];//表示最大的或和
            res[1][i] = nums[i];//表示最小的或和
            res[2][i] = nums[i];//表示最大的与和
            res[3][i] = nums[i];//表示最小的与和
            int j = i - 1;
            if (j >= 0) {
                res[0][i] = Math.max(res[0][i], Math.max(res[0][i] | res[0][j], res[0][j]));
                res[1][i] = Math.min(res[1][i], Math.min(res[1][i] | res[1][j], res[1][j]));
                res[2][i] = Math.max(res[2][i], Math.max(res[2][i] & res[2][j], res[2][j]));
                res[3][i] = Math.min(res[3][i], Math.min(res[3][i] & res[3][j], res[3][j]));
            }
        }
        int sum = 0;
        for (int i = 0; i < 4; i++) {
            sum += res[i][n - 1];
        }
        return sum;

    }