Рубрики

Максимальная сумма элементов из каждой строки в матрице

Учитывая матрицу, найдите максимальную сумму, которую мы можем получить, выбрав только один элемент из каждой строки. Условие — элемент, выбранный из n-й строки, должен быть строго больше, чем элемент из (n-1) -ной строки, иначе элемент не должен быть взят из строки. Если возможно, выведите сумму, иначе выведите -1.

Примеры :

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)

Подход: — Можно просто запустить цикл из последней строки, получить оттуда наибольший элемент, скажем, что prev_max, и сохранить запись для минимальной разницы между элементами строки чуть выше нее, если какой-либо элемент найден с положительной разницей, затем добавить это к prev_max, иначе выведите -1. Продолжайте один и тот же процесс для каждой строки.

C ++

// Программа CPP для поиска построчного максимального элемента
// сумма с учетом элементов в порядке возрастания.
#include <bits/stdc++.h>
#define N 3

using namespace std;

  
// Функция для выполнения поставленной задачи

int getGreatestSum(int a[][N])

{

    // Получение максимального элемента из последней строки

    int prev_max = 0;

    for (int j = 0; j < N; j++)

        if (prev_max < a[N - 1][j])

            prev_max = a[N - 1][j];

  

    // Сравнение с элементами вышеприведенных строк

    int sum = prev_max;

    for (int i = N - 2; i >= 0; i--) {

  

        // Максимум текущей строки.

        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];

  

        // Если бы мы не могли элемент меньше

        // чем prev_max.

        if (curr_max == INT_MIN)

            return -1;

  

        prev_max = curr_max;

        sum += prev_max;

    }

    return sum;

}

  
// Код драйвера

int 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-программа для поиска построчного максимума
// сумма элементов с учетом элементов в
// увеличение порядка.

class GFG {

  

    static final int N = 3;

  

    // Функция для выполнения поставленной задачи

    static int getGreatestSum(int a[][])

    {

  

        // Получение максимального элемента из

        // последний ряд

        int prev_max = 0;

  

        for (int j = 0; j < N; j++)

            if (prev_max < a[N - 1][j])

                prev_max = a[N - 1][j];

  

        // Сравнение с элементами

        // из вышеуказанных строк

        int sum = prev_max;

  

        for (int i = N - 2; i >= 0; i--) {

  

            // Максимум текущей строки.

            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];

  

            // Если бы мы не могли элемент меньше

            // чем prev_max.

            if (curr_max == -2147483648)

                return -1;

  

            prev_max = curr_max;

            sum += prev_max;

        }

  

        return sum;

    }

  

    // Программа драйвера для проверки вышеуказанной функции

    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));

    }

}

  
// Этот код предоставлен Anant Agarwal.

python3

# Программа Python для поиска
# построчный максимальный элемент
# сумма с учетом элементов
# в порядке возрастания.

  

N = 3

  
# Функция для выполнения поставленной задачи

def getGreatestSum(a):

  

    # Получение максимума

    # элемент из последней строки

    prev_max = 0

    for j in range(N):

        if (prev_max < a[N - 1][j]):

            prev_max = a[N - 1][j]

  

    # Сравнивая это с

    # элементы выше строк

    sum = prev_max

    for i in range(N - 2, -1, -1):

  

        # Максимум текущей строки.

        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 (curr_max == -2147483648):

            return -1

  

        prev_max = curr_max

        sum = sum + prev_max

      

    return sum

  
# Код драйвера

  

a = [ [ 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))

      
# Этот код добавлен
# Анант Агарвал.

C #

// C # Программа для поиска построчного максимума
// сумма элементов с учетом элементов в
// увеличение порядка.

using System;

  

class GFG {

  

    static int N = 3;

  

    // Функция для выполнения поставленной задачи

    static int getGreatestSum(int[, ] a)

    {

  

        // Получение максимального элемента из

        // последний ряд

        int prev_max = 0;

  

        for (int j = 0; j < N; j++)

            if (prev_max < a[N - 1, j])

                prev_max = a[N - 1, j];

  

        // Сравнение с элементами

        // из вышеуказанных строк

        int sum = prev_max;

  

        for (int i = N - 2; i >= 0; i--) {

  

            // Максимум текущей строки.

            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];

  

            // Если бы мы не могли элемент меньше

            // чем prev_max.

            if (curr_max == -2147483648)

                return -1;

  

            prev_max = curr_max;

            sum += prev_max;

        }

  

        return sum;

    }

  

    // Программа для водителя

    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));

    }

}

  
// Этот код предоставлен vt_m.

PHP

<?php
// PHP программа для поиска
// построчный максимальный элемент
// сумма с учетом элементов
// в порядке возрастания.

  

$N = 3; 

  
// Функция для выполнения поставленной задачи

function getGreatestSum( $a)

{

    global $N;

      

    // Получаем максимум

    // элемент из последней строки

    $prev_max = 0;

  

    for ($j = 0; $j < $N; $j++)

        if ($prev_max < $a[$N - 1][$j])

            $prev_max = $a[$N - 1][$j];

  

    // Сравнение с

    // элементы вышеуказанных строк

    $sum = $prev_max;

    for ($i = $N - 2; $i >= 0; $i--) 

    {

  

        // Максимум текущей строки.

        $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];

  

        // Если бы мы не могли элемент

        // меньше чем prev_max.

        if ($curr_max == PHP_INT_MIN)

            return -1;

  

        $prev_max = $curr_max;

        $sum += $prev_max;

    }

    return $sum;

}

  
// Код драйвера

$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";

  
// Этот код предоставлен anuj_67.
?>


Выход :

18
15

Рекомендуемые посты:

Максимальная сумма элементов из каждой строки в матрице

0.00 (0%) 0 votes