/home/toolbox/public_html/solutions/5/507/a.c
1 #include <stdio.h>
2 #include <string.h>
3 #include <sys/types.h>
4 #include <sys/stat.h>
5 #include <fcntl.h>
6 #include <stdlib.h>
7 #include <math.h>
8 #include <stdint.h>
9
10 #define TRUE (1 == 1)
11 #define FALSE (1 != 1)
12
13 #define DEBUG if (FALSE)
14
15 /* fprintf(stderr, "functionName: message", varslist); */
16
17 /*
18 * Author: Isaac Traxler
19 * Date: 2019-02-06
20 * Purpose: fun
21 * Problem: 507 - Jill Rides Again
22 */
23
24 /*
25 * This template reads data a specified number of times.
26 */
27
28 #define MAX_STOPS 20010
29
30 int numberOfTimes;
31 int stops;
32 int nice[MAX_STOPS];
33 int best;
34 int bestStart;
35 int bestStop;
36
37 void init()
38 {
39 /* FUNCTION init */
40 scanf("%d ", &numberOfTimes);
41 } /* FUNCTION init */
42
43 void dump()
44 {
45 /* FUNCTION dump */
46 } /* FUNCTION dump */
47
48 void getInput()
49 {
50 /* FUNCTION getInput */
51 int i;
52
53 scanf(" %d ", &stops);
54 for (i=0; (stops-1)>i; i++)
55 {
56 /* get each niceness */
57 scanf(" %d ", &nice[i]);
58 } /* get each niceness */
59 } /* FUNCTION getInput */
60
61 void kadane()
62 {
63 /* FUNCTION kadane */
64 int j;
65 int tot;
66 int localStart;
67 int localStop;
68
69 best = nice[0];
70 tot = nice[0];
71 localStart = 0;
72 localStop = 0;
73 bestStart = 0;
74 bestStop = 0;
75 for (j=1; (stops-1)>j; j++)
76 {
77 /* each cell */
78 DEBUG printf("(j=%d) (tot=%d) (nice[%d]=%d)\n", j, tot, j, nice[j]);
79 /* if next item increases tot, add it to tot, otherwise start over at item */
80 localStop = j;
81 if (nice[j] > (tot+nice[j]))
82 {
83 /* start over */
84 localStart = j;
85 tot = nice[j];
86 } /* start over */
87 else
88 {
89 /* keep going */
90 tot = tot + nice[j];
91 } /* keep going */
92 /* if curent rolling sum is better, keep it */
93 if (tot > best)
94 {
95 /* new best answer */
96 bestStart = localStart;
97 bestStop = localStop;
98 best = tot;
99 } /* new best answer */
100 if (tot == best)
101 {
102 /* same amount -- take if same start */
103 if (localStart == bestStart)
104 {
105 /* just got a zero sum chunk so keep it */
106 bestStop = localStop;
107 } /* just got a zero sum chunk so keep it */
108 if ((localStop - localStart) > (bestStop - bestStart))
109 {
110 /* found a longer route of same value -- take it */
111 bestStart = localStart;
112 bestStop = localStop;
113 } /* found a longer route of same value -- take it */
114 } /* same amount -- take if same start */
115 } /* each cell */
116 } /* FUNCTION kadane */
117
118 void process(int r)
119 {
120 /* FUNCTION process */
121 kadane();
122 if (0 < best)
123 {
124 /* found an interesting route */
125 printf("The nicest part of route %d is between stops %d and %d\n", r, bestStart+1, bestStop+2);
126 } /* found an interesting route */
127 else
128 {
129 /* bad place */
130 printf("Route %d has no nice parts\n", r);
131 } /* bad place */
132
133 } /* FUNCTION process */
134
135 int main()
136 {
137 /* main */
138 int i;
139
140 init();
141 for (i=0; i<numberOfTimes; i++)
142 {
143 /* while */
144 getInput();
145 process(i+1);
146 } /* while */
147
148 return EXIT_SUCCESS;
149 } /* main */
150
151