3.31 腾讯笔试 第四题

动态规划，dp[i][j]表示前i个数分j段的最大异或和

用异或交换律的性质，x^y = z 等价于 x^z = y，然后类似前缀和维护一个从前往后异或的数组，然后用交换律的性质可以在O(1)时间里很快的找到某个区间所有元素的异或和，然后就记忆化搜索

public static void getMax(int[] nums,int k){ int len=nums.length; long[] preXor=new long[len]; preXor[0]=nums[0]; for (int i = 1; i < len; i++) { preXor[i]^=nums[i]; } //dp[i][j] 表示 分为 i 段 时 以 j为结尾的 最大异或和 long[][] dp = new long[k + 1][len]; dp[1]=preXor; for (int i = 2; i <=k ; i++) { for (int j = i-1; j < len; j++) { long val=0; for (int l = j-1; l >=0 ; l--) { /* 多了一个数字 j , 这个数字必然在 分段的最后一段中 ,最后一段分多长呢? 只能遍历 preXor[j]^preXor[l] 再 加 前面的数字 分为 i-1段 时的最大值 */ val=Math.max(val,dp[i-1][l]+(preXor[j]^preXor[l])); } dp[i][j]=val; } } System.out.println(dp[k][len-1]); }