1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
|
/*
Challenge 202
Task 2: Widest Valley
Submitted by: E. Choroba
Given a profile as a list of altitudes, return the leftmost widest valley.
A valley is defined as a subarray of the profile consisting of two parts:
the first part is non-increasing and the second part is non-decreasing.
Either part can be empty.
Example 1
Input: 1, 5, 5, 2, 8
Output: 5, 5, 2, 8
Example 2
Input: 2, 6, 8, 5
Output: 2, 6, 8
Example 3
Input: 9, 8, 13, 13, 2, 2, 15, 17
Output: 13, 13, 2, 2, 15, 17
Example 4
Input: 2, 1, 2, 1, 3
Output: 2, 1, 2
Example 5
Input: 1, 3, 3, 2, 1, 2, 3, 3, 2
Output: 3, 3, 2, 1, 2, 3, 3
*/
#include <iostream>
#include <vector>
void largest_valey(const std::vector<int>& heights, std::vector<int>& valey) {
int l1 = 0, r1 = -1; // initial interval
// find largest valey
int heights_size = static_cast<int>(heights.size());
for (int c = 0; c < heights_size; c++) { // center of valey
int l = c; // left
while (l-1 >= 0 && heights[l-1] >= heights[l])
l--;
int r = c; // right
while (r+1 < heights_size && heights[r+1] >= heights[r])
r++;
if (r - l + 1 > r1 - l1 + 1) {
l1 = l;
r1 = r;
}
}
// return valey in heights array
valey.resize(r1-l1+1);
memmove(&valey[0], &heights[l1], (r1-l1+1)*sizeof(int));
}
int main(int argc, char* argv[]) {
argv++; argc--;
if (argc < 2) {
fputs("Usage: ch-2 height...\n", stderr);
return EXIT_FAILURE;
}
std::vector<int> heights;
for (int i = 0; i < argc; i++)
heights.push_back(atoi(argv[i]));
std::vector<int> valey;
largest_valey(heights, valey);
for (size_t i = 0; i < valey.size(); i++)
std::cout << valey[i] << " ";
std::cout << std::endl;
return EXIT_SUCCESS;
}
|
