C++での単一の反転後に最大隣接絶対値の合計を見つけるプログラム

numsという番号のリストがあり、リスト内のサブリストを最大で1回反転できるとします。この操作を実行した後、

$ \ displaystyle \ sum \ Limits_ {i =0} ^ {n-2} | nums [i + 1]-[nums [i] | $

したがって、入力がnums =[2、4、6]の場合、出力は6になります。たとえば、[4、6]を逆にすると、リストは[2、6、4]になり、値は|になります。 2 − 6 | + | 6 − 4 | =6

これを解決するには、次の手順に従います-

• numsのサイズが<=1の場合、-

  • 0を返す

• ans：=0

• n：=numsのサイズ

• 初期化i：=1の場合、i

  • ans：=ans + | nums [i] − nums [i − 1] |

• orig：=ans

• 初期化i：=1の場合、i

  • ans：=ansとorigの最大値− |（nums [i] − nums [i + 1] | + | nums [0] − nums [i + 1] |

  • ans：=ansとorigの最大値− |（nums [i] − nums [i − 1] | + | nums [n − 1] − nums [i − 1] |

• pp：=− | nums [1] − nums [0] |

• pm：=− | nums [1] − nums [0] |

• mp：=− | nums [1] − nums [0] |

• mm：=− | nums [1] − nums [0] |

• 初期化j：=2の場合、j

  • jerror：=| nums [j + 1] − nums [j] |

  • ans：=ansの最大値および（orig + pp − jerror − nums [j] − nums [j + 1]）

  • ans：=ansの最大値および（orig + pm − jerror − nums [j] + nums [j + 1]）

  • ans：=ansの最大値および（orig + mp − jerror + nums [j] − nums [j + 1]）

  • ans：=ansの最大値および（orig + mm − jerror + nums [j] + nums [j + 1]）

  • pp：=ppの最大値と− | nums [j] − nums [j − 1] |

  • pm：=pmの最大値と− | nums [j] − nums [j − 1] |

  • mp：=mpの最大値と− | nums [j] − nums [j − 1] |

  • mm：=mmの最大値および− | nums [j] − nums [j − 1] |

• ansを返す

理解を深めるために、次の実装を見てみましょう-

例

#include <bits/stdc++.h>
using namespace std;
int solve(vector<int>& nums) {
   if (nums.size() <= 1)
   return 0;
   int ans = 0;
   int n = nums.size();
   for (int i = 1; i < n; i++) {
      ans += abs(nums[i] − nums[i − 1]);
   }
   int orig = ans;
   for (int i = 1; i < n − 1; i++) {
      ans = max(ans, orig − abs(nums[i] − nums[i + 1]) +
      abs(nums[0] − nums[i + 1]));
      ans = max(ans, orig − abs(nums[i] − nums[i − 1]) + abs(nums[n
   − 1] − nums[i − 1]));
   }
   int pp = −abs(nums[1] − nums[0]) + nums[0] + nums[1];
   int pm = −abs(nums[1] − nums[0]) + nums[0] − nums[1];
   int mp = −abs(nums[1] − nums[0]) − nums[0] + nums[1];
   int mm = −abs(nums[1] − nums[0]) − nums[0] − nums[1];
   for (int j = 2; j < n − 1; j++) {
      int jerror = abs(nums[j + 1] − nums[j]);
      ans = max(ans, orig + pp − jerror − nums[j] − nums[j + 1]);
      ans = max(ans, orig + pm − jerror − nums[j] + nums[j + 1]);
      ans = max(ans, orig + mp − jerror + nums[j] − nums[j + 1]);
      ans = max(ans, orig + mm − jerror + nums[j] + nums[j + 1]);
      pp = max(pp, −abs(nums[j] − nums[j − 1]) + nums[j − 1] +
      nums[j]);
      pm = max(pm, −abs(nums[j] − nums[j − 1]) + nums[j − 1] −
      nums[j]);
      mp = max(mp, −abs(nums[j] − nums[j − 1]) − nums[j − 1] +
      nums[j]);
      mm = max(mm, −abs(nums[j] − nums[j − 1]) − nums[j − 1] −
      nums[j]);
   }
   return ans;
}
int main(){
   vector<int> v = {2, 4, 6};
   cout << solve(v);
}

入力

{2, 4, 6}

出力

6