Computer >> Máy Tính >  >> Lập trình >> C ++

Chương trình tìm tổng giá trị tuyệt đối liền kề lớn nhất sau khi đảo ngược một lần trong C ++

Giả sử chúng ta có một danh sách các số được gọi là num và chúng ta có thể đảo ngược bất kỳ danh sách con nào trong danh sách cùng một lúc. Sau khi thực hiện thao tác này, chúng ta phải tìm giá trị lớn nhất có thể có của

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

Vì vậy, nếu đầu vào là nums =[2, 4, 6], thì đầu ra sẽ là 6, còn khi đảo ngược [4, 6] chúng ta sẽ nhận được danh sách là [2, 6, 4] và giá trị | 2 - 6 | + | 6 - 4 | =6

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

  • nếu kích thước của nums <=1, thì -

    • trả về 0

  • ans:=0

  • n:=kích thước của nums

  • để khởi tạo i:=1, khi i

    • ans:=ans + | nums [i] - nums [i - 1] |

  • orig:=ans

  • để khởi tạo i:=1, khi tôi

    • ans:=tối đa ans và orig - | (nums [i] - nums [i + 1] | + | nums [0] - nums [i + 1] |

    • ans:=tối đa ans và orig - | (nums [i] - nums [i - 1] | + | nums [n - 1] - nums [i - 1] |

  • pp:=- | nums [1] - nums [0] |

  • chiều:=- | nums [1] - nums [0] |

  • mp:=- | nums [1] - nums [0] |

  • mm:=- | nums [1] - nums [0] |

  • để khởi tạo j:=2, khi j

    • giật:=| nums [j + 1] - nums [j] |

    • ans:=tối đa ans và (orig + pp - jerror - nums [j] - nums [j + 1])

    • ans:=tối đa ans và (orig + pm - jerror - nums [j] + nums [j + 1])

    • ans:=tối đa ans và (orig + mp - jerror + nums [j] - nums [j + 1])

    • ans:=tối đa ans và (orig + mm - jerror + nums [j] + nums [j + 1])

    • pp:=tối đa của pp và - | nums [j] - nums [j - 1] |

    • pm:=tối đa pm và - | nums [j] - nums [j - 1] |

    • mp:=tối đa của mp và - | nums [j] - nums [j - 1] |

    • mm:=tối đa là mm và - | nums [j] - nums [j - 1] |

  • trả lại ans

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

Ví dụ 

#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);
}

Đầu vào 

{2, 4, 6}

Đầu ra 

6