Maximum Sub Square Sum

PKJ

 Coding Problem Keys 

 Maximum Sub Square Sum 

 Problem Statement 

Given a square matrix of size N x N where each cell is filled with a number between -9 and 9. A sub square of size k is any set of k contiguous columns and k contiguous rows. For any sub square, the sum of elements in its cells is called a sub square sum. Given the N x N square, write a program to find the maximum sub square sum. Note that a 1 x 1 square (k = 1) is not considered a sub square.

 Boundary Condition(s) 

2 <= N <= 1000

 Input Format 

The first line contains the value of N.
The next N lines contain N integers each separated by space(s).

 Output Format 

The first line contains the maximum sub square sum.

 Example Input/Output 1 

 Input 

4
2 -8 4 -6
7 1 -5 3
-9 7 6 5
8 3 2 -4

 Output 

20

 Explanation 

The 2 by 2 square sums are
2 -8 -4
6 9 9
9 18 9

The 3 by 3 square sums are
5 7
20 18

And the 4 by 4 square sum is 16. Hence the maximum sub square sum is 20.

 Example Input/Output 2 

 Input 

3
1 1 0
1 2 2
3 0 4

 Output 

14

 Explanation 

As all the entries are non-negative, the 3 by 3 sub square (which has a sum of 14) is the maximum.

 Max Execution Time Limit: 5000 millisecs 

 Solution 

 Programming Language: C Language 

#include <stdio.h>
#include <stdlib.h>
int maxsubsum(int n, int mat[n][n], int k){
    int stripsum[n][n];
    int i,j;
    for(j=0;j<n;j++){
        int sum=0;
        for(i=0;i<k;i++)
            sum+=mat[i][j];
        stripsum[0][j]=sum;
        for(i=1;i<=n;i++){
            sum+=mat[i+k-1][j]-mat[i-1][j];
            stripsum[i][j]=sum;
        }
    }
    int max=-99999;
    for(i=0;i<=n-k;i++){
        int sum=0;
        for(j=0;j<k;j++){
            sum+=stripsum[i][j];
        }
        if(sum>max)
            max=sum;
        for(j=1;j<=n-k;j++){
            sum+=stripsum[i][j+k-1]-stripsum[i][j-1];
            if(sum>max)
                max=sum;
        }
    }
    return max;
}
int main() {
    int n,i,k,j;
    scanf("%d",&n);
    int mat[n][n];
    for(i=0;i<n;i++){
        for(j=0;j<n;j++){
            scanf("%d",&mat[i][j]);
        }
    }
    int max=-99999;
    for(k=2;k<=n;k++){
        int sum=maxsubsum(n,mat,k);
        if(sum>max){
            max=sum;
        }
    }
    printf("%d",max);
}

// Published By PKJCODERS

 (Note: Incase If the code doesn't Pass the output kindly comment us with your feedback to help us improvise.) 

Comments

Post a Comment

Popular Posts

Turning Book Pages

PKJ
 Coding Problem Keys   Turning Book Pages   Problem Statement  A book can be turned either from front or from the back. When we open a book always we have the page 1 always on the right. The book pages must always be turned one by one instead of multiple pages at once. Each page has two sides, front and back. Hence the last page may have only front side depending on the total number of pages N in the book (If N is even, it will have both sides printed else if N is odd only the front side will be printed). Now Manoj wants to navigate to a page P in the book by turning the least minimum pages either from front or back. Please help Manoj by completing the program as per the given requirement.  Boundary Condition(S)  1 <= N <= 10000 1 <= P <= N  Input Format  The first line will contain the value of N which represents the total number of pages in the book. The second line will contain the value of P which represents the page to b...
Click to Continue...

Jooney's Amusement Park

PKJ
 Coding Problem Keys   Jooney's Amusement Park   Problem Statement  In the amusement park at Jooney's amusement, there is a "Weighted Maze" challenge. This consist of a set of East West roads and North South roads (referred to as up down roads). There are N intersections and each intersection has a block of iron bar, the weight of which is given. You enter the maze at the top left corner. The exit from the maze is at the bottom right corner. Movement at any intersection is to the right or down provided a road exists in that direction. At each Intersection you pass through, you must exchange the weight in your cart with the weight of the bar at the intersection if it is heavier than the weight in you have in the cart. The objective is to determine a path through the maze along the roads so that one can exit the maze with minimum weight in the cart.  Input Format  The first line contains the number of intersections N.  Output Format  The f...
Click to Continue...

Shift Largest Digit - Sum

PKJ
 Coding Problem Keys   Shift Largest Digit - Sum   Problem Statement  The program must accept N integers as the input. For each integer X among the N integers, the program must shift the largest digit in X to the left . If the largest digit occurs more than once in an integer, the program must shift the last occurring largest digit to the left. Then the program must print the sum of the N modified integers as the output.  Input Format  The first line contains N. The second line contains N integers separated by a space.  Output Format  The first line contains an integer representing the sum of the N modified integers.  Boundary Condition(s)  2 <= K <= N  <= 1000 1 <= Each integer value <= 10 ⁵  Example Input/Output 1   Input  4 4613 234 6969 2990   Output  25822   Explanation  Here N = 4 . After shifting the largest digit in each integer to the left, the integers bec...
Click to Continue...

Reverse Column - First and Last

PKJ
 Coding Problem Keys   Reverse Column - First and Last   Problem Statement  The program must accept an integer matrix of size RxC as the input. The program must reverse all the elements in the column if the first and last elements of the column are same. Then the program must print the modified matrix as the output.  Input Format  The first line contains the value of R and C separated by space. The next R lines contain each C elements separated by space(s).  Output Format  The first R lines contain each C elements separated by space.  Boundary Condition(s)  2 <= R, C <= 50 -999 <= Each element of the matrix <= 999  Example Input/Output 1   Input  5 4 11 7 5 19 4 13 16 10 9 9 13 0 7 5 17 8 11 8 5 12   Output  11 7 5 19 7 13 17 10 9 9 13 0 4 5 16 8 11 8 5 12  Explanation  The elements in the first column are 11, 4, 9, 7 and 11. Here the first and the last elements are same. So ...
Click to Continue...

String With Most Vowels

PKJ
 Coding Problem Keys   String With Most Vowels   Problem Statement  Two Strings S1 and S2 are given as input. The program must print the string with the most number of vowels. If two strings have the same number of vowels, print the string with greater length.  Boundary Condition(s)  1 <= Length of Strings <=1000  Input Format  The first line S1 and S2 separated by space(s).  Output Format  The first line contains a string.  Example Input/Output 1   Input  adder divider  Output  divider  Example Input/Output 2   Input  important welcome  Output  important  Note:  Max Execution Time Limit: 5000 millisecs   Solution   Programming Language: Java Language  import java.util.* ; public class Hello { public static int vowel (String s){ int x= 0 ; s=s. toLowerCase (); char ch; for ( in...
Click to Continue...

Multiply Three Numbers

PKJ
 Kick Start   Multiply Three Numbers   Problem Statement  Accept three numbers and print their product.  Example Input/Output 1   Input  2 5 10  Output  100  Example Input/Output 2   Input  6 3 7  Output  126  Note:  Max Execution Time Limit: 4000 millisecs   Solution   Programming Language: C Language  #include<stdio.h> #include <stdlib.h> int main (){ int X, Y, Z; scanf( "%d %d %d" , &X, &Y, &Z); printf( "%d" , X*Y*Z); } //Published By PKJCODERS  Programming Language: C++ Language  #include <iostream> using namespace std; int main (){ int X, Y, Z; cin >> X >> Y >> Z; cout << X*Y*Z; } //Published By PKJCODERS  Programming Language: Java Language  import java.util.* ; public class Hello { public static void main (String[]...
Click to Continue...