Snippets

Lucas José Kreutz Alves rykr: Untitled snippet

Created by Lucas José Kreutz Alves
/**
* Problem: 108 - Maximum Sum
*/

#include <iostream>
#include <iomanip>

using namespace std;

int main() {
	int n = 0;
	int A[101][101]    = {0};
	int sums[101][101] = {0};

	while(cin >> n) {
		// read the matrix and create the auxiliary sum matrix
		for(int i=1; i<=n; i++) {
			for(int j=1; j<=n; j++) {
				cin >> A[i][j];
				// each position is the sum of all values in its left to the top
				sums[i][j] = sums[i-1][j] + sums[i][j-1] - sums[i-1][j-1] + A[i][j];
			}
		}

		// calculate all subsets and save the maximum sum using the auxiliary matrix
		long long int max_sum = -127;
		for(int i=1; i<=n; i++) {
			for(int j=1; j<=n; j++) {
				for(int k=i; k<=n; k++) {
					for(int l=j; l<=n; l++) {
						long long int sum = -127;

						// calculate the sums of the subsets using the auxiliary matrix
						// subtracting the areas that are not in the subset
						sum = sums[k][l] - sums[i-1][l] - sums[k][j-1] + sums[i-1][j-1];

						if(sum > max_sum) {
							max_sum = sum;
						}
					}
				}
			}
		}

		cout << max_sum << endl;
	}
}

Comments (0)

HTTPS SSH

You can clone a snippet to your computer for local editing. Learn more.