Maximum XOR Score Subarray Queries

想法：須先觀察找到規律，可以找到 nums[start ... end] 的 XOR score 會等於 nums[start ... end - 1] ^ nums[ start + 1 ... end] 的結果
為了要找到subarray的最大值，用一個max_score的陣列儲存結果；而每個max_score陣列都只要考慮本身的 nums[start ... end] 以及 max_score[ start ... end - 1 ] , 
max_score[start + 1 ... end] 即可，因為後兩者都已經在之前被算過了，可以代表該範圍的最大數值，而start ... end 也只需要多考慮 start ... end 的本身數值即可

Time Complexity : O(n ^ 2) for finding the dp array and max score array
Space Complexity : O(n ^ 2) for dp array , max score array 

class Solution {
public:
    vector<int> maximumSubarrayXor(vector<int>& nums, vector<vector<int>>& queries) {
        int n = nums.size() ; 
        vector< vector<int> > dp( n , vector<int>(n) ) ; 
        vector< vector<int> > max_score( n , vector<int>(n) ) ;
        // base case 
        for(int i = 0 ; i < n ; i++) {
                dp[i][i] = nums[i] ;
                max_score[i][i] = dp[i][i] ;
        }

        // construct dp array 
        for( int len = 2 ; len <= n ; len++ ) {
            for( int start = 0 ; start + len - 1 < n ; start++ ) {
                dp[start][ start + len - 1 ] 
                    = dp[start][start + len - 2] ^ dp[start + 1][start + len - 1] ;
                max_score[start][start + len - 1] = dp[start][start + len - 1] ;
            }
        }

        for( int len = 2 ; len <= n ; len++ ) {
            for(int start = 0 ; start + len - 1 < n ; start++) {
                max_score[start][start + len - 1] 
                    = max( {max_score[start][start + len - 1] 
                    , max_score[start][start + len - 2] 
                    , max_score[start + 1][start + len - 1]} ) ;
            }
        }
        
        vector<int> answer ; 
        for( auto &i : queries ) {
            answer.push_back( max_score[ i[0] ][ i[1] ] ) ;
        }

        return answer ;
    }
};