50159. Stock Price
難度：4.2/5
好複雜。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#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>
int n;
int8_t arr[40000];
int max_len = -1;
int max_left_len = -1;
int max_idx = -1;
int is_mono(){
int pos = 0, neg = 0;
for(int i = 0; i < n - 1; i++){
if(arr[i] == 1) pos = 1;
if(arr[i] == -1) neg = 1;
if(pos && neg) return 0;
}
return 1;
}
void deal(int up, int down, int idx){
int len = up + down + 1;
if(len > max_len){
max_len = len, max_left_len = up, max_idx = idx - up - down + 2;
}
else if(len == max_len && up > max_left_len){
max_left_len = up, max_idx = idx - up - down + 2;
}
}
void find_mountain(int8_t arr[], int n){
int inc = 0, drc = 0;
int last_inc = 0, last_drc = 0;
for(int i = 0; i < n - 1; i++){
if(arr[i] == 1){
inc++;
if(drc != 0) last_drc = drc, drc = 0;
deal(last_drc, inc, i);
}
else if(arr[i] == -1){
drc++;
if(inc != 0) last_inc = inc, inc = 0;
deal(last_inc, drc, i);
}
}
}
int main(){
n = 1;
int last = 0;
if(scanf("%d", &last) == EOF){
printf("0\n"); return 0;
}
int num;
while(scanf("%d", &num) != EOF){
if(last < num) arr[n - 1] = 1;
else arr[n - 1] = -1;
n++;
last = num;
}
if(is_mono()){
printf("0\n"); return 0;
}
else{
find_mountain(arr, n);
printf("%d %d\n", max_len, max_idx);
}
}
// v
// i i d d i i
// 0 1 2 1 0 1 2