-
Notifications
You must be signed in to change notification settings - Fork 4
/
Copy pathMax_door_number_sum.c
193 lines (158 loc) · 11.7 KB
/
Max_door_number_sum.c
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
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
/*
Max Door Number Sum
There is a town in which H houses are situated in each of the S streets. Each house has a door number which is an positive integer. So these S*H door numbers form a matrix.
From any house you can navigate to the house in the east(right) or to the house located south (bottom). Thus the navigation ends when there is no house in the east or in the south.
The program must print the maximum possible sum of the door numbers traversed during the above mentioned navigation.
Input Format:
The first line will S and H separated by a space.
Next S lines will each contain H positive integer values (representing the door numbers) separated by a space.
Output Format:
The first line will contain the maximum possible sum of the door numbers traversed.
Boundary Conditions:
2 <= S,H <= 500
1 <= DoorNumber <= 10000
Example Input/Output 1:
Input:
3 3
15 25 30
45 25 60
70 75 10
Output:
215
Explanation:
The maximum possible sum of 215 is obtained when we follow 15->45->70->75->10
Example Input/Output 2:
Input:
4 4
4 10 10 4
4 9 9 4
2 2 10 1
9 9 2 7
Output:
52
Explanation:
The maximum possible sum of 52 is obtained when we follow 4->10->10->9->10->2->7
Other Test Cases:
=================================================================================================================
20 15
2145 1742 3361 8587 9197 6157 2955 4044 2465 4161 6145 6463 3733 9207 4992
5523 1986 4059 1205 9374 6785 7631 8824 7445 7962 3849 688 7394 4179 6205
1462 3599 2856 2306 1821 6865 2741 9327 6301 1522 112 650 5154 344 8414
6823 1867 1811 6411 3219 4183 5660 7417 1180 9654 2786 4812 3837 7981 774
8268 3811 2893 384 1201 2261 4605 9065 917 920 4378 1758 1226 1662 8146
301 8747 1020 7421 4494 7202 3828 4648 5427 6879 8858 1114 5482 3781 9278
3597 3009 5524 613 1400 9518 4072 2138 6542 5952 5486 996 1895 2353 3910
8903 5211 5437 2355 3895 6062 1833 3839 7854 1760 5839 8007 6022 5640 7068
3471 6212 18 8160 4504 1850 5470 314 1223 4808 9076 9880 8140 4712 1893
3398 5385 5385 836 132 1865 6346 2360 7170 9637 4237 8138 2198 5029 8076
6930 1745 2175 1175 4580 295 255 717 5846 8159 327 367 9059 1704 6696
8334 1170 3996 6466 5222 5370 6769 8159 9192 9306 3018 676 7294 7049 2604
5778 3696 5384 9949 8894 9004 5194 605 3237 4750 7807 4720 8115 1274 5488
1786 6960 1884 5752 7586 5900 4032 2836 6931 4132 1716 9827 5013 7352 2255
3137 3022 8883 3891 9518 8251 4595 621 9378 3937 3993 7076 2493 4415 7192
8711 8246 562 2354 1489 7000 7016 8866 825 5469 3627 5364 533 2960 621
1998 4607 3653 4329 8667 8990 2200 6376 5061 3077 9743 7870 1307 6651 2021
9622 8772 8506 1011 2340 6192 2082 8881 2932 9264 3872 785 9724 5557 7055
1222 4014 105 102 5557 1584 7596 1209 2693 5006 4988 2641 1541 3705 4046
7830 741 5521 9716 3312 7993 4212 9364 9892 5857 3495 1598 9788 2811 3297
Output:
221821
=================================================================================================================
40 35
6762 3586 2178 1628 9019 1234 319 2933 6075 5999 4664 9516 6024 1133 4391 1359 5539 1276 7893 2313 6206 7267 2114 847 7180 9151 4728 6165 1270 1672 5104 3585 3156 7541 127
3997 5865 651 1860 4823 7074 2331 8549 1436 1242 2802 6357 8954 3828 7910 8040 9308 4430 4561 2784 901 7985 3642 4345 9961 883 783 1204 3617 5002 3024 4244 9685 6369 6165
3305 4659 8812 9581 7470 2640 5501 4939 9349 7166 8392 1619 7871 7314 5778 611 494 3371 7383 7147 931 2747 7819 5665 7645 9012 9157 1499 5630 4267 3989 8968 3006 7582 5955
2921 4336 1202 8633 7115 8792 3766 691 5771 5704 3817 4941 6754 5177 119 2361 5457 442 4616 2088 3670 7581 366 2176 6383 9742 7069 4532 8611 1283 8246 5332 8845 8742 7212
6555 429 3283 1493 6029 9472 6843 1866 3022 5548 2589 7327 8864 1274 9373 6419 28 9471 652 8779 6613 7825 3755 5243 7230 5849 187 2419 2220 9284 2692 7598 8737 6117 6493
1948 914 4772 8284 5522 8533 1164 944 6372 9121 3396 2855 6708 2217 2694 974 4485 1399 4700 8442 1598 1931 4570 1929 4066 7129 2389 994 6841 9167 5410 6243 9174 3796 8712
6697 3822 6104 5619 9422 3189 7667 2161 3036 7934 6423 6188 4189 1024 1688 7774 5486 2041 4707 3074 447 640 6248 9610 5276 7663 9906 5166 8075 8237 933 8693 39 6051 5523
8505 3696 5667 3099 8988 3642 7688 1683 5097 2080 7197 1366 8527 9478 2799 8132 2060 7726 5677 9375 385 3832 2169 8387 9592 139 5881 3861 8289 612 5181 7767 278 7716 7842
1507 5628 1500 2716 990 2642 5882 4874 3537 8647 9812 1573 2389 2859 1489 2584 9645 6913 335 3370 2230 8457 5603 6914 6630 9375 2597 3022 2551 5478 8652 2383 7497 3999 5063
9779 6112 8300 7288 7314 6850 6552 1819 5222 2275 7619 987 9282 4701 4965 9042 3146 9570 3799 3662 6882 5101 5588 696 3976 5656 6782 7544 5205 9550 7181 799 8422 8964 6
665 5828 5043 9059 8079 4457 3743 7520 305 8829 1048 6148 8628 4110 3883 4270 3396 3381 6288 8837 4626 5337 6421 4048 3542 8720 3928 9066 5309 3923 3240 5943 6959 5349 5062
4370 4906 6410 7334 4989 5502 529 7233 7080 4900 8349 3812 7296 916 5523 7498 217 7034 1670 402 895 8580 7218 5218 2919 3429 9289 1477 2546 8220 8664 4981 9173 6403 1123
7441 9826 1959 2020 7324 303 8598 2791 3098 3256 2622 2580 1049 2234 9431 3613 8406 4690 9176 4445 4592 9855 5314 139 1762 4401 8192 558 7647 2161 1214 9046 5 225 6502
2038 914 6667 577 4685 8657 4265 8646 9695 5877 1734 4971 8895 5668 1916 1207 6530 1840 7350 1605 4707 9315 5538 9430 9666 7919 3166 7305 4654 5582 5821 6853 44 2571 2091
552 5161 6973 7549 6469 3646 1310 4618 5180 5490 8642 1617 5416 6291 717 4426 8198 3823 9799 9158 4479 4757 7389 7978 7711 2979 8468 1225 7258 2729 1112 9419 5038 7380 6058
6466 9611 439 2423 293 3491 3211 2082 4586 2970 4391 4628 6693 5925 9097 5043 8981 984 5398 1208 4949 2396 8362 1359 7719 476 8257 7455 2675 9774 7068 2151 2474 4008 3060
63 9028 1981 3036 7384 5673 834 3435 9322 8179 5302 131 582 4822 9141 1440 8283 5538 732 9303 7904 5109 5165 4664 524 4063 9640 4517 3383 9152 6650 2496 1698 8659 4826
5480 7932 9880 2129 9731 9504 9629 1138 9278 8908 161 6125 4579 5038 3476 1507 1394 7499 1477 9386 5289 3475 922 2445 5979 650 106 3056 6839 9190 4756 6985 2649 6961 5693
6880 216 3896 699 4129 9832 3231 554 8835 9809 3391 3562 7731 8686 3637 1963 2485 1237 8598 2029 9346 1234 1541 8368 5766 1040 1835 8118 1144 5024 7049 1326 2508 9437 8370
9186 7221 2639 1687 394 8758 3483 6459 2085 6524 6388 1316 7088 772 6836 6557 2007 9466 3918 9968 196 9873 6163 8715 607 7821 7974 6821 716 3878 2192 9388 3170 3851 3325
2311 3651 340 4983 8117 6928 1097 6642 7234 5547 5842 4712 9010 4499 2857 8691 8341 7898 9487 982 7374 8030 5626 7977 7813 4831 2092 8790 7108 7549 6116 3104 2484 4885 1223
1159 115 3753 6561 5151 8788 5873 1447 1431 7982 3651 5501 8695 2055 4578 9162 6763 3400 3556 7235 8761 6824 8205 2015 4914 7179 1984 6094 9810 784 8773 796 3919 3342 5566
4832 4984 7597 7531 3270 8053 3849 3226 6618 7564 7764 3214 1508 5753 7591 7486 6849 8971 4267 5065 317 5440 5350 6255 3756 8498 5917 9035 4022 7486 5575 3992 7969 1048 4032
7557 6081 8057 8365 4319 3348 9293 8041 7477 4022 7078 9841 6672 1146 3551 1820 3650 7275 1846 9033 9694 7765 1483 4420 7440 58 2961 4264 95 6640 4189 3265 1371 6314 5858
2002 89 7712 6262 2408 3236 6146 1602 1736 3605 674 3469 2615 6434 8081 5095 5166 284 7694 238 6443 2508 8131 8301 1780 1384 8383 8867 8556 1957 2731 1267 7567 1857 3798
1596 2247 4930 8236 7162 3697 6900 9467 2673 4617 2843 7666 8120 6320 8716 7786 9586 5500 4202 6866 2519 8375 7485 2730 2709 2763 6652 2991 8509 478 4576 9285 8498 5555 1970
5294 4161 1476 5697 7979 665 322 812 4643 2122 1915 8758 8333 2159 516 7054 6026 1232 4184 6836 3747 4352 4971 6066 7058 3903 9464 4469 3844 3254 3035 9383 7867 436 9493
5588 2288 1649 5817 2030 1417 3329 2824 5149 599 1214 363 7108 1021 1056 6959 5164 648 9478 4544 8577 4599 976 8428 8823 7154 2727 8818 2318 8396 4281 5548 3651 698 7929
6064 2951 7629 809 7217 1103 7329 7928 8387 1014 1980 2245 8971 3858 9926 5509 6868 3466 8124 8120 3909 4657 1126 7721 8596 8228 269 3366 4745 5391 737 2769 5510 348 6872
1774 4700 5751 3769 2860 2005 2869 8704 7451 5102 5479 5458 9093 9331 1180 873 4470 99 6456 270 5379 606 7230 2321 3211 304 8721 2341 8703 5128 3560 8894 26 7953 7276
3210 2665 3585 9216 5580 8053 5684 3318 6166 4539 3186 7202 4706 9139 4923 808 6842 9913 1709 4028 9370 5414 8783 1977 5379 7822 5043 5578 40 4913 4384 6960 2743 8398 1936
7765 1844 4891 4256 8804 9837 185 511 5892 6593 370 2056 7767 8286 5607 899 298 5444 3621 3915 713 4193 1630 1942 5317 8217 6642 3948 8195 8096 5543 7019 1953 4029 6150
9970 1749 2443 273 1570 9096 8010 4395 3401 925 6069 991 8955 1501 3444 1439 6677 8346 587 8636 6728 1473 3943 8356 5640 5995 946 3673 6688 1463 4601 2122 1847 9481 8424
5834 6114 4943 8997 1565 821 4457 5382 3565 6456 1847 8833 9667 363 3031 8605 9219 6341 7562 1966 1236 9520 4946 3074 2893 9541 6577 8381 7917 4500 4321 6199 9474 9531 7220
608 2831 9723 7413 7547 1694 5358 5267 997 9027 5899 5601 3500 7997 4348 8252 6338 4941 5546 6203 1576 5080 9365 3408 8981 5754 7443 4998 1511 4528 8723 1942 3289 2804 4893
8768 6986 8847 7376 1559 6895 2601 5686 8554 5430 2830 7103 731 7452 8128 2414 6225 5956 9910 4931 3057 9459 6937 9469 6300 357 1966 3255 3818 6384 640 9077 912 9051 8078
9290 4981 238 849 8760 5872 2621 4907 1155 4858 8333 4309 9482 4250 9297 3010 9451 2087 5618 6215 5871 4506 1436 1015 5984 9502 9418 1072 6168 781 6471 9063 7792 3214 3034
1552 3686 7622 9687 5053 7292 3377 6217 7921 1465 6138 340 5623 6005 6536 3967 8029 543 5652 8933 9922 8898 9341 4353 9144 9360 8986 3417 6239 8201 8039 7038 7339 6597 1582
9960 5007 9658 3511 2337 3831 3812 7461 7463 278 9761 9835 4702 9047 2714 1824 805 6771 6406 5801 2491 9806 6682 7227 9296 4500 9026 4083 6202 628 419 655 4475 7835 2147
7861 8310 2105 8719 1902 454 6500 6699 6488 6314 1816 8291 5126 2532 8733 5871 9377 9393 4181 6262 9721 7079 3591 5701 7184 2939 868 9450 3038 9802 4557 2723 3470 6103 2144
Output:
535351
In this problem we need to check all the possibilities ( so it is very hard to check all the possibilities )
so how to solve it "Dynamic Programming"
why Dynamic Programming?
the solution are dependent on previous solution
how to solve it?
1)construct the table which contain the maximum value generated in each path
2)Before selecting new path check previous path which has maximum value
3)continue the step untill full table is constructed
4)the answer will be last element of the matrix
This approach is called bottom-up parsing in Dynamic programming knowning dp[0] and find dp[n]
reference
http://www.geeksforgeeks.org/solve-dynamic-programming-problem/
http://www.geeksforgeeks.org/tabulation-vs-memoizatation/
*/
#include<stdio.h>
int m,n;
int isValid(int east,int south){ //check if the given values are valid
if((east<n) && (south<m))
return 0;
else
return 1;
}
int find_max(int num1,int num2){ // function ro find maximum of two numbers
return (num1>num2)?num1:num2;
}
int construct_table(int a[m][n],int max_table[m][n],int south,int east){ // Costruct the Max table
if(isValid(east,south)==1)
return -1;
if(east==0 && south==0)
return a[south][east];
if(east==0)
return max_table[south-1][east]+a[south][east];
if(south==0)
return max_table[south][east-1]+a[south][east];
return a[south][east] + find_max(max_table[south-1][east],max_table[south][east-1]); //Get the maximum path
}
int main(){
scanf("%d%d",&m,&n);
int a[m][n],max_table[m][n],i,j;
for(i=0;i<m;i++){
for(j=0;j<n;j++){
scanf("%d",&a[i][j]);
max_table[i][j]=-1;
}
}
for(i=0;i<m;i++){
for(j=0;j<n;j++){
max_table[i][j]=construct_table(a,max_table,i,j);
//printf("%d ",max_table[i][j]); //uncomment this line to see the value of max matrix
}
//printf("\n");
}
printf("%d",max_table[m-1][n-1]); // print the largest sum
return 0;
}