fork download
  1. #include <iostream>
  2. #include <vector>
  3. #include <algorithm>
  4. using namespace std;
  5.  
  6. // 计算当前数组中最长的山脉长度
  7. int longestMountain(const vector<int>& arr) {
  8. int n = arr.size();
  9. if (n < 3) return 0; // 山脉至少需要3个元素
  10.  
  11. int max_len = 0;
  12.  
  13. for (int peak = 1; peak < n - 1; peak++) {
  14. // 检查是否可以成为山峰(严格递增到peak,然后严格递减)
  15. if (arr[peak-1] < arr[peak] && arr[peak] > arr[peak+1]) {
  16. int left = peak - 1;
  17. int right = peak + 1;
  18.  
  19. // 向左扩展
  20. while (left > 0 && arr[left-1] < arr[left]) {
  21. left--;
  22. }
  23.  
  24. // 向右扩展
  25. while (right < n-1 && arr[right] > arr[right+1]) {
  26. right++;
  27. }
  28.  
  29. // 计算山脉长度
  30. max_len = max(max_len, right - left + 1);
  31. }
  32. }
  33.  
  34. return max_len;
  35. }
  36.  
  37. int main() {
  38. int T;
  39. cin >> T;
  40.  
  41. while (T--) {
  42. int n;
  43. cin >> n;
  44. vector<int> arr(n);
  45.  
  46. for (int i = 0; i < n; i++) {
  47. cin >> arr[i];
  48. }
  49.  
  50. // 初始最长山脉长度
  51. int max_length = longestMountain(arr);
  52.  
  53. // 尝试修改每一个元素为可能的值
  54. for (int i = 0; i < n; i++) {
  55. int original = arr[i];
  56.  
  57. // 尝试修改为左右邻居的值(更可能形成山脉)
  58. if (i > 0) {
  59. arr[i] = arr[i-1];
  60. max_length = max(max_length, longestMountain(arr));
  61. }
  62. if (i < n-1) {
  63. arr[i] = arr[i+1];
  64. max_length = max(max_length, longestMountain(arr));
  65. }
  66.  
  67. // 特殊情况:如果是边界元素,尝试设置为中间值
  68. if (i == 0 && n > 1) {
  69. arr[i] = (arr[i+1] - 1);
  70. max_length = max(max_length, longestMountain(arr));
  71. }
  72. if (i == n-1 && n > 1) {
  73. arr[i] = (arr[i-1] - 1);
  74. max_length = max(max_length, longestMountain(arr));
  75. }
  76.  
  77. arr[i] = original; // 恢复原值
  78. }
  79.  
  80. cout << max_length << endl;
  81. }
  82.  
  83. return 0;
  84. }
  85.  
Success #stdin #stdout 0s 5320KB
stdin
3
5
3 6 2 3 1
6
1 1 4 5 1 4
10
7 8 3 5 6 1 2 4 9 10
stdout
4
5
5