地址：

1537. 最大得分

状态：超时

解法：双指针

代码：双指针

  1. class Solution {
  2. public:
  3.     int maxSum(vector<int>& nums1, vector<int>& nums2) {
  4.         long sum1 = 0, sum2 = 0;
  5.         long res = 0;
  6.         int i = 0, j = 0;
  7.         while(i < nums1.size() && j < nums2.size()){
  8.             if(nums1[i] == nums2[j]){
  9.                 sum1 = (max(sum1, sum2) + nums1[i]);
  10.                 sum2 = sum1;
  11.                 i++;
  12.                 j++;
  13.             }
  14.             else if(nums1[i] < nums2[j]){
  15.                 sum1 += nums1[i];
  16.                 i++;                
  17.             }
  18.             else{
  19.                 sum2 += nums2[j];
  20.                 j++;
  21.             }            
  22.         }
  23.         while(i < nums1.size()){
  24.             sum1 += nums1[i];
  25.             i++;
  26.         }
  27.         while(j < nums2.size()){
  28.             sum2 += nums2[j];
  29.             j++;
  30.         }
  31.         res = max(sum1, sum2);
  32.         return res % ((int)pow(10, 9) + 7 );
  33.     }
  34. };

超时代码：

  1. class Solution {
  2. public:
  3.     int max;
  4.     int maxSum(vector<int>& nums1, vector<int>& nums2) {
  5.         max = 0;
  6.         dfs(nums1,0,nums2,0,0,1);
  7.         dfs(nums1,0,nums2,0,0,2);
  8.         return max;
  10.     }
  11.     void dfs(vector<int>& nums1, int i, vector<int>& nums2, int j,int sum, int flag){
  12.         if(i==nums1.size() && flag == 1)
  13.             return;
  14.         if(j == nums2.size() && flag == 2)
  15.             return;
  16.         int k;
  17.         if(flag == 1){
  18.             for(k = j;k<nums2.size();k++)
  19.                 if(nums1[i] == nums2[k])
  20.                     break;
  21.             sum = (sum +nums1[i]) % 1000000007;
  22.             if((i == nums1.size() - 1 && k == nums2.size()) || (i == nums1.size() - 1 && j == nums2.size() - 1)){
  23.                 if(sum > max) max = sum;
  24.             }else if(k == nums2.size()){
  25.                 dfs(nums1,i+1,nums2,j,sum,flag);
  26.             }else if(k < nums2.size()){
  27.                 dfs(nums1,i+1,nums2,j,sum,1);
  28.                 dfs(nums1,i+1,nums2,k+1,sum,2);
  29.             }
  30.         }else if(flag == 2){
  31.             for(k = i;k<nums1.size();k++)
  32.                 if(nums2[j] == nums1[k])
  33.                     break;
  34.             sum = (sum +nums2[j]) % 1000000007;
  35.             if((j == nums2.size() - 1 && k == nums1.size()) || (j == nums2.size() - 1 && i == nums1.size() - 1)){
  36.                 if(sum > max) max = sum;
  37.             }else if(k == nums1.size()){
  38.                 dfs(nums1,i,nums2,j+1,sum,flag);
  39.             }else if(k < nums1.size()){
  40.                 dfs(nums1,k+1,nums2,j+1,sum,1);
  41.                 dfs(nums1,i,nums2,j+1,sum,2);
  42.             }
  43.         }
  45.     }
  46. };