程序在C ++中单次反转后查找最大相邻绝对值总和

  • Z时代
  • 2024-01-10
  • 分类：综合

假设我们有一个称为nums的数字列表，并且我们最多可以反转一次列表中的任何子列表。执行完此操作后，我们必须找到最大可能值

$\ 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

  • 回答：= 0

  • n：= nums的大小

  • 对于初始化i：= 1，当i <n时，更新（将i增加1），-

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

  • orig：= ans

  • 对于初始化i：= 1，当i <n − 1，更新（i增加1）时，-

    • 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 <n − 1，更新（j增加1）时，-

    • 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

以上是 程序在C ++中单次反转后查找最大相邻绝对值总和 的全部内容， 来源链接： utcz.com/z/337966.html

回到顶部