โจทย์: อาร์เรย์ A ขนาด n A[i] เป็น local minimum ถ้าน้อยกว่าทั้งสองข้าง อย่างเคร่งครัด เป็น local maximum ถ้ามากกว่าทั้งสองข้าง A[0] และ A[n-1] ไม่นับ หาจำนวน local extrema
Input: A=[1,5,2,5] → Output: 2 (5 ตำแหน่ง 1 เป็น maxima, 2 ตำแหน่ง 2 เป็น minima)
ขั้นตอนแก้
sum := 0
for i := 1 to n-2:
if (A[i] < A[i-1] && A[i] < A[i+1]) || (A[i] > A[i-1] && A[i] > A[i+1]):
sum++
return sumตัวอย่างโค้ด
#include <bits/stdc++.h>
using namespace std;
int solve(vector<int> A) {
int sum = 0, n = A.size();
for (int i = 1; i < n-1; i++)
if ((A[i] < A[i-1] && A[i] < A[i+1]) || (A[i] > A[i-1] && A[i] > A[i+1]))
sum++;
return sum;
}
int main() {
vector<int> A = {1,5,2,5};
cout << solve(A) << endl;
}Input
{1,5,2,5}Output
2
