Given a matrix, find the maximum sum we can have by selecting just one element from every row. Condition is element selected from nth row must be strictly greater than element from (n-1)th row, else no element must be taken from row. Print the sum if possible else print -1.
Examples :
Input :
1 2 3
1 2 3
7 8 9
Output : 14 (2 + 3 + 9) (values we are adding are strictly increasing)Input :
4 2 3
3 2 1
1 2 2\
Output : -1
(No subsequent increasing elements can be picked from consecutive rows)
Approach:- One can simply run the loop from last row, get the greatest element from there say it prev_max, and keep record for the minimum difference among the elements of the row just above it, if any element found with positive difference, then add it to prev_max else print -1. Continue the same process for every row.
Implementation:
C++
// CPP Program to find row-wise maximum element// sum considering elements in increasing order.#include <bits/stdc++.h>#define N 3using namespace std;// Function to perform given taskint getGreatestSum(int a[][N]){ // Getting the maximum element from last row int prev_max = 0; for (int j = 0; j < N; j++) if (prev_max < a[N - 1][j]) prev_max = a[N - 1][j]; // Comparing it with the elements of above rows int sum = prev_max; for (int i = N - 2; i >= 0; i--) { // Maximum of current row. int curr_max = INT_MIN; for (int j = 0; j < N; j++) if (prev_max > a[i][j] && a[i][j] > curr_max) curr_max = a[i][j]; // If we could not get an element smaller // than prev_max. if (curr_max == INT_MIN) return -1; prev_max = curr_max; sum += prev_max; } return sum;}// Driver codeint main(){ int a[3][3] = { { 1, 2, 3 }, { 4, 5, 6 }, { 7, 8, 9 } }; cout << getGreatestSum(a) << endl; int b[3][3] = { { 4, 5, 6 }, { 4, 5, 6 }, { 4, 5, 6 } }; cout << getGreatestSum(b) << endl; return 0;} |
Java
// Java Program to find row-wise maximum// element sum considering elements in// increasing order.class GFG { static final int N = 3; // Function to perform given task static int getGreatestSum(int a[][]) { // Getting the maximum element from // last row int prev_max = 0; for (int j = 0; j < N; j++) if (prev_max < a[N - 1][j]) prev_max = a[N - 1][j]; // Comparing it with the elements // of above rows int sum = prev_max; for (int i = N - 2; i >= 0; i--) { // Maximum of current row. int curr_max = -2147483648; for (int j = 0; j < N; j++) if (prev_max > a[i][j] && a[i][j] > curr_max) curr_max = a[i][j]; // If we could not an element smaller // than prev_max. if (curr_max == -2147483648) return -1; prev_max = curr_max; sum += prev_max; } return sum; } // Driver Program to test above function public static void main(String arg[]) { int a[][] = { { 1, 2, 3 }, { 4, 5, 6 }, { 7, 8, 9 } }; System.out.println(getGreatestSum(a)); int b[][] = { { 4, 5, 6 }, { 4, 5, 6 }, { 4, 5, 6 } }; System.out.println(getGreatestSum(b)); }}// This code is contributed by Anant Agarwal. |
Python3
# Python Program to find# row-wise maximum element# sum considering elements# in increasing order.N = 3# Function to perform given taskdef getGreatestSum(a): # Getting the maximum # element from last row prev_max = 0 for j in range(N): if (prev_max < a[N - 1][j]): prev_max = a[N - 1][j] # Comparing it with the # elements of above rows sum = prev_max for i in range(N - 2, -1, -1): # Maximum of current row. curr_max = -2147483648 for j in range(N): if (prev_max > a[i][j] and a[i][j] > curr_max): curr_max = a[i][j] # If we could not an element smaller # than prev_max. if (curr_max == -2147483648): return -1 prev_max = curr_max sum = sum + prev_max return sum# Driver codea = [ [ 1, 2, 3 ], [ 4, 5, 6 ], [ 7, 8, 9 ] ]print(getGreatestSum(a))b = [ [ 4, 5, 6 ], [ 4, 5, 6 ], [ 4, 5, 6 ] ]print(getGreatestSum(b)) # This code is contributed# by Anant Agarwal. |
C#
// C# Program to find row-wise maximum// element sum considering elements in// increasing order.using System;class GFG { static int N = 3; // Function to perform given task static int getGreatestSum(int[, ] a) { // Getting the maximum element from // last row int prev_max = 0; for (int j = 0; j < N; j++) if (prev_max < a[N - 1, j]) prev_max = a[N - 1, j]; // Comparing it with the elements // of above rows int sum = prev_max; for (int i = N - 2; i >= 0; i--) { // Maximum of current row. int curr_max = -2147483648; for (int j = 0; j < N; j++) if (prev_max > a[i, j] && a[i, j] > curr_max) curr_max = a[i, j]; // If we could not an element smaller // than prev_max. if (curr_max == -2147483648) return -1; prev_max = curr_max; sum += prev_max; } return sum; } // Driver Program public static void Main() { int[, ] a = { { 1, 2, 3 }, { 4, 5, 6 }, { 7, 8, 9 } }; Console.WriteLine(getGreatestSum(a)); int[, ] b = { { 4, 5, 6 }, { 4, 5, 6 }, { 4, 5, 6 } }; Console.WriteLine(getGreatestSum(b)); }}// This code is contributed by vt_m. |
PHP
<?php// PHP Program to find // row-wise maximum element// sum considering elements// in increasing order.$N = 3; // Function to perform given taskfunction getGreatestSum( $a){ global $N; // Getting the maximum // element from last row $prev_max = 0; for ($j = 0; $j < $N; $j++) if ($prev_max < $a[$N - 1][$j]) $prev_max = $a[$N - 1][$j]; // Comparing it with the // elements of above rows $sum = $prev_max; for ($i = $N - 2; $i >= 0; $i--) { // Maximum of current row. $curr_max = PHP_INT_MIN; for ( $j = 0; $j < $N; $j++) if ($prev_max > $a[$i][$j] and $a[$i][$j] > $curr_max) $curr_max = $a[$i][$j]; // If we could not an element // smaller than prev_max. if ($curr_max == PHP_INT_MIN) return -1; $prev_max = $curr_max; $sum += $prev_max; } return $sum;}// Driver code$a = array(array(1, 2, 3), array(4, 5, 6), array(7, 8, 9)); echo getGreatestSum($a), "\n";$b = array(array(4, 5, 6), array(4, 5, 6), array(4, 5, 6)); echo getGreatestSum($b), "\n";// This code is contributed by anuj_67.?> |
Javascript
<script>// JavaScript Program to find row-wise maximum// element sum considering elements in// increasing ordererslet N = 3; // Function to perform given task function getGreatestSum(a) { // Getting the maximum element from // last row let prev_max = 0; for (let j = 0; j < N; j++) if (prev_max < a[N - 1][j]) prev_max = a[N - 1][j]; // Comparing it with the elements // of above rows let sum = prev_max; for (let i = N - 2; i >= 0; i--) { // Maximum of current row. let curr_max = -2147483648; for (let j = 0; j < N; j++) if (prev_max > a[i][j] && a[i][j] > curr_max) curr_max = a[i][j]; // If we could not an element smaller // than prev_max. if (curr_max == -2147483648) return -1; prev_max = curr_max; sum += prev_max; } return sum; } // Driver Code let a = [[ 1, 2, 3 ], [ 4, 5, 6 ], [ 7, 8, 9 ]]; document.write(getGreatestSum(a) + "<br/>"); let b = [[ 4, 5, 6 ], [ 4, 5, 6 ], [4, 5, 6 ]]; document.write(getGreatestSum(b)); </script> |
Output
18 15
Time complexity: O(N2)
Auxiliary space: O(1)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
