/home/toolbox/public_html/solutions/1/108/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 <stdint.h>
7 #include <math.h>
8 #include <stdlib.h>
9
10 #define TRUE (1 == 1)
11 #define FALSE (1 != 1)
12
13 #define DEBUG if (FALSE)
14
15 #define MAX_SIZE 105
16
17 /*
18 * Author: Isaac Traxler
19 * Date: 2014-10-29
20 * Purpose: fun
21 * Problem: 108 - Maximum Sum - more to be done
22 */
23
24 /*
25 * This template reads data until a terminating value is reached.
26 */
27
28 int dim;
29 int a[MAX_SIZE][MAX_SIZE];
30 int tmp[MAX_SIZE];
31
32 void init()
33 {
34 /* FUNCTION init */
35 } /* FUNCTION init */
36
37 void dump()
38 {
39 /* FUNCTION dump */
40 } /* FUNCTION dump */
41
42 int maximum(int a, int b)
43 {
44 /* FUNCTION maximum */
45 if (a > b)
46 return a;
47 else
48 return b;
49 } /* FUNCTION maximum */
50
51 int getInput()
52 {
53 /* FUNCTION getInput */
54 int i;
55 int j;
56 int moreToDo = FALSE;
57
58 i = scanf(" %d ", &dim);
59 if (0 < i)
60 {
61 /* Read in a dimension */
62 moreToDo = TRUE;
63 for (i=0; i<dim; i++)
64 for (j=0; j<dim; j++)
65 {
66 /* get each value */
67 scanf(" %d ", &a[i][j]);
68 } /* get each value */
69 } /* Read in a dimension */
70 return moreToDo;
71 } /* FUNCTION getInput */
72
73 int kadane()
74 {
75 /* FUNCTION kadane */
76 int j;
77 int best;
78 int tot;
79
80 /* example
81 1 0 3 4 -1 7 -10 5 2 5 -30 10 9
82 tot 1 1 4 8 7 14 4 9 11 16 -14 10 19
83 best 1 1 4 8 8 14 14 14 14 16 16 16 19
84 */
85 best = tmp[0];
86 tot = tmp[0];
87 for (j=1; dim>j; j++)
88 {
89 /* each cell */
90 /* if next item increases tot, add it to tot, otherwise start over at item */
91 tot = maximum(tmp[j], tot+tmp[j]);
92 /* if curent rolling sum is better, keep it */
93 best = maximum(best, tot);
94 } /* each cell */
95 return best;
96 } /* FUNCTION kadane */
97
98 void initTmp()
99 {
100 /* FUNCTION initTmp */
101 int i;
102
103 for (i=0; dim>i; i++)
104 {
105 /* for each location */
106 tmp[i] = 0;
107 } /* for each location */
108 } /* FUNCTION initTmp */
109
110 void process()
111 {
112 /* FUNCTION process */
113 int mx;
114 int i;
115 int i1;
116 int c;
117 int best;
118
119 mx = a[0][0];
120 for (i=0; dim>i; i++)
121 {
122 /* i will be the first row to use per pass*/
123 initTmp();
124 for (i1=i; dim>i1; i1++)
125 {
126 /* do from ith row to dim */
127 for (c=0; dim>c; c++)
128 {
129 /* add each column */
130 tmp[c] = tmp[c] + a[i1][c];
131 } /* add each column */
132 best = kadane();
133 mx = maximum(mx, best);
134 } /* do from ith row to dim */
135 } /* i will be the first row to use per pass*/
136
137 printf("%d\n", mx);
138 } /* FUNCTION process */
139
140 int main ()
141 {
142 /* main */
143 int moreToDo;
144
145 init();
146 moreToDo = getInput();
147 while (moreToDo)
148 {
149 /* process as long as input continues */
150 process();
151 moreToDo = getInput();
152 } /* process as long as input continues */
153
154 return EXIT_SUCCESS;
155 } /* main */
156