/home/toolbox/public_html/solutions/1/108/e.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
31 void init()
32 {
33 /* FUNCTION init */
34 } /* FUNCTION init */
35
36 void dump()
37 {
38 /* FUNCTION dump */
39 } /* FUNCTION dump */
40
41 int getInput()
42 {
43 /* FUNCTION getInput */
44 int i;
45 int j;
46 int moreToDo = FALSE;
47
48 i = scanf(" %d ", &dim);
49 if (0 < i)
50 {
51 /* Read in a dimension */
52 moreToDo = TRUE;
53 for (i=0; i<dim; i++)
54 for (j=0; j<dim; j++)
55 {
56 /* get each value */
57 scanf(" %d ", &a[i][j]);
58 } /* get each value */
59 } /* Read in a dimension */
60 return moreToDo;
61 } /* FUNCTION getInput */
62
63 int findMax(int x1, int x2, int y1, int y2)
64 {
65 /* FUNCTION findMax */
66 int i;
67 int j;
68 int tot = 0;
69
70 for (i=x1; i<=x2; i++)
71 for (j=y1; j<=y2; j++)
72 {
73 /* each cell */
74 tot = tot + a[i][j];
75 } /* each cell */
76 return tot;
77 } /* FUNCTION findMax */
78
79 void process()
80 {
81 /* FUNCTION process */
82 int mx;
83 int i1, i2;
84 int j1, j2;
85 int tmp;
86 int prev;
87
88 mx = a[0][0];
89 for (i1=0; i1<dim; i1++)
90 {
91 /* brute force i start */
92 for (i2=i1; i2<dim; i2++)
93 {
94 /* brute force i end */
95 for (j1=0; j1<dim; j1++)
96 {
97 /* j start */
98 prev = a[i2][j1];
99 for (j2=j1; j2<dim; j2++)
100 {
101 /* end point of j */
102 tmp = findMax(i1, i2, j1, j2);
103 if (tmp >= prev)
104 {
105 /* still going up */
106 prev = tmp;
107 printf("[%d-%d,%d-%d] = %d\n", i1, i2, j1, j2, tmp);
108 if (tmp > mx)
109 {
110 mx = tmp;
111 }
112 } /* still going up */
113 else
114 {
115 j2 = dim + 1;
116 }
117 } /* end point of j */
118 } /* j start */
119 } /* brute force i end */
120 } /* brute force i start */
121
122 printf("%d\n", mx);
123 } /* FUNCTION process */
124
125 int main ()
126 {
127 /* main */
128 int moreToDo;
129
130 init();
131 moreToDo = getInput();
132 while (moreToDo)
133 {
134 /* process as long as input continues */
135 process();
136 moreToDo = getInput();
137 } /* process as long as input continues */
138
139 return EXIT_SUCCESS;
140 } /* main */
141