Given an array of size n, we have to find 3 peak values and 3 trough values in the array such that each peak values are separated by another peak value by n entries.
Similarly, each trough value must be n days separated from the other trough values. For eg:
int arr[] = {1, 5, 6, 4, 3, 3, 10, 2, 8, 6, 11, 4, 10};
int distance = 2;
In above example, peak values are – 6, 10 and 11 (which are 2 indices apart).
valley values are – 1, 3 and 2 (which are 2 indices apart).
Let’s have a look at the program which solves above problem.
/*****************************************************************************************
*
* Find peak and troughs in 60 items where,
* 1) Each peak/troughs should have been atleast +/- 10 days
*
*****************************************************************************************/
#include "iostream"
float prices[] = {341,
328.85,
353,
355.6,
358.55,
350.55,
353.55,
370.65,
364.3,
360.8,
357.2,
355.2,
359.85,
372.7,
367,
371.15,
367.1,
368.15,
378.55,
383.9,
381.1,
387.7,
387.6,
389.6,
383.65,
395.65,
405.05,
394.2,
394.95,
390.15,
407.25,
406.25,
395.6,
389.5,
399.55,
415.2,
411.75,
402.35,
406.95,
393.15,
390.15,
392.25,
394.8,
397.05,
393.1,
355.1,
335.95,
333.1,
310.7,
282.1,
282.35,
275.65,
280.95,
283.7,
294.85,
302.55,
298.6,
294.45,
303.85,
307.25};
#define DISTANCE 10
#define CHECK_RANGE(X) (X > peak_1_low && X < peak_1_high) || ((X > peak_2_low && X < peak_2_high))
#define CHECK_RANGE_TROUGH(X) (X > trough_1_low && X < trough_1_high) || ((X > trough_2_low && X < trough_2_high))
#define ASSIGN_VALUE(X) (X == 1 ? peak_1: X == 2 ? peak_2: peak_3)
#define ASSIGN_VALUE_TROUGH(X) (X == 1 ? trough_1: X == 2 ? trough_2: trough_3)
using namespace std;
void find_peak_troughs (float* arr, int size)
{
/* Below items will contain the indexes */
int peak_1 = 0;
int peak_2 = 0;
int peak_3 = 0;
int trough_1 = 0;
int trough_2 = 0;
int trough_3 = 0;
for (int i = 1; i < 4; i++)
{
int index = -1;
int peak_1_low = (peak_1 == 0 ? 0 : peak_1 - DISTANCE);
int peak_1_high = (peak_1 == 0 ? 0 : peak_1 + DISTANCE);
int peak_2_low = (peak_2 == 0 ? 0 : peak_2 - DISTANCE);
int peak_2_high = (peak_2 == 0 ? 0 : peak_2 + DISTANCE);
for (int j = 0; j < size; j++)
{
if (CHECK_RANGE (j)) {
continue;
}
if (index == -1 || arr[index] < arr[j]) {
index = j;
}
}
ASSIGN_VALUE(i) = index;
}
for (int i = 1; i < 4; i++)
{
int index = -1;
int trough_1_low = (trough_1 == 0 ? 0 : trough_1 - DISTANCE);
int trough_1_high = (trough_1 == 0 ? 0 : trough_1 + DISTANCE);
int trough_2_low = (trough_2 == 0 ? 0 : trough_2 - DISTANCE);
int trough_2_high = (trough_2 == 0 ? 0 : trough_2 + DISTANCE);
for (int j = 0; j < size; j++)
{
if (CHECK_RANGE_TROUGH (j)) {
continue;
}
if (index == -1 || arr[index] > arr[j]) {
index = j;
}
}
ASSIGN_VALUE_TROUGH(i) = index;
}
cout << "Peak 1 index: " << peak_1 << " Value: " << arr[peak_1] << endl;
cout << "Peak 2 index: " << peak_2 << " Value: " << arr[peak_2] << endl;
cout << "Peak 3 index: " << peak_3 << " Value: " << arr[peak_3] << endl;
cout << "Trough 1 index: " << trough_1 << " Value: " << arr[trough_1] << endl;
cout << "Trough 2 index: " << trough_2 << " Value: " << arr[trough_2] << endl;
cout << "Trough 3 index: " << trough_3 << " Value: " << arr[trough_3] << endl;
}
int main ()
{
find_peak_troughs (prices, sizeof(prices)/sizeof(prices[0]));
}
Let’s analyze the output of above program.
Peak 1 index: 35 Value: 415.2
Peak 2 index: 25 Value: 395.65
Peak 3 index: 13 Value: 372.7
Trough 1 index: 51 Value: 275.65
Trough 2 index: 1 Value: 328.85
Trough 3 index: 11 Value: 355.2