Рубрики

Найти максимальную сумму строго увеличивающегося подмассива

Дан массив натуральных чисел. Найдите максимальную сумму строго возрастающих подмассивов. Обратите внимание, что эта задача отличается от задач подпоследовательности с максимальной суммой подмассива и с максимальной суммой увеличения .

Примеры:

Input  : arr[] = {1, 2, 3, 2, 5, 1, 7}
Output : 8
Explanation :  Some Strictly increasing subarrays are 
               {1, 2, 3} sum = 6, 
               {2, 5} sum = 7, 
               {1, 7} sum 8 
               Maximum Sum = 8 

Input : arr[] = {1, 2, 2, 4}
Output: 6
Explanation : Increasing subarray with maximum sum
              is 6.

Простое решение состоит в том, чтобы сгенерировать все возможные подмассивы и для каждой подмассивной проверки проверять, строго ли увеличивается подмассив или нет. Если подмассив строго увеличивается, то мы вычисляем сумму и обновляем max_sum. Временная сложность O (n 2 ).

Эффективное решение этой проблемы занимает O (n) времени. Идея состоит в том, чтобы отслеживать максимальную сумму и текущую сумму. Для каждого элемента arr [i], если он больше, чем arr [i-1], мы добавляем его к текущей сумме. Иначе arr [i] является отправной точкой другого потенциального кандидата для подмассива, увеличивающего максимальную сумму, поэтому мы обновляем текущую сумму как массив. Но перед обновлением текущей суммы мы обновляем максимальную сумму, если требуется.

Let input array be 'arr[]' and size of array be 'n'

Initialize : 
max_sum = 0 // used to store the maximum sum 
current_sum = arr[0] // used to compute current sum 

// Traverse array starting from second element
i goes from 1 to n-1

    // Check if it is strictly increasing then we 
    // update current_sum.
    current_sum = current_sum + arr[i]

    // else strictly increasing subarray breaks and 
    // arr[i] is starting point of next potential
    // subarray
    max_sum = max(max_sum, current_sum)
    current_sum = arr[i]

return max(max_sum, current_sum)    

Ниже приведена реализация вышеуказанной идеи.

C ++

// C / C ++ программа для поиска максимальной суммы строго
// увеличение подмассивов
#include<iostream>

using namespace std;

  
// Возвращает максимальную сумму строго возрастающего
// подмассивы

int maxsum_SIS(int arr[] , int n)

{

    // Инициализируем max_sum быть 0

    int max_sum = 0;

  

    // Инициализируем текущую сумму как arr [0]

    int current_sum = arr[0] ;

  

    // Обход элементов массива после первого элемента.

    for (int i=1; i<n ; i++ )

    {

        // обновляем current_sum для строго увеличивающегося подмассива

        if (arr[i-1] < arr[i])

            current_sum = current_sum + arr[i];

  

        else // строго увеличивающийся разрыв подмассива

        {

            // обновляем max_sum и current_sum;

            max_sum = max(max_sum, current_sum);

            current_sum = arr[i];

        }

    }

  

    return max(max_sum, current_sum);

}

  
// Драйвер программы

int main()

{

    int arr[] = {1, 2, 2, 4};

    int n = sizeof(arr)/sizeof(arr[0]);

  

    cout << "Maximum sum : " << maxsum_SIS(arr , n);

    return 0;

}

Джава

// Java программа для поиска максимальной суммы строго
// увеличение подмассивов

  

public class GFG {

  
// Возвращает максимальную сумму строго возрастающего
// подмассивы

    static int maxsum_SIS(int arr[], int n) {

        // Инициализируем max_sum быть 0

        int max_sum = 0;

  

        // Инициализируем текущую сумму как arr [0]

        int current_sum = arr[0];

  

        // Обход элементов массива после первого элемента.

        for (int i = 1; i < n; i++) {

            // обновляем current_sum для строго увеличивающегося подмассива

            if (arr[i - 1] < arr[i]) {

                current_sum = current_sum + arr[i];

            } else // строго увеличивающийся разрыв подмассива

            {

                // обновляем max_sum и current_sum;

                max_sum = Math.max(max_sum, current_sum);

                current_sum = arr[i];

            }

        }

  

        return Math.max(max_sum, current_sum);

    }

  
// драйверная программа

    public static void main(String[] args) {

        int arr[] = {1, 2, 2, 4};

        int n = arr.length;

        System.out.println("Maximum sum : " + maxsum_SIS(arr, n));

    }

}

  
// Этот код предоставлен 29AjayKumar

python3

# Python3 программа для поиска максимальной суммы строго
# увеличение подмассивов

  
# Возвращает максимальную сумму строго увеличивающегося
# подмассивы

def maxsum_SIS(arr, n):

    # Инициализировать max_sum будет 0

    max_sum = 0

   

    # Инициализировать текущую сумму как обр [0]

    current_sum = arr[0

   

    # Обход элементов массива после первого элемента.

    for i in range(1,n):

        # обновить current_sum для строго увеличивающегося массива

        if (arr[i-1] < arr[i]):

            current_sum = current_sum + arr[i]

   

   

        else:

            # строго увеличивающийся разрыв подмассива

            # update max_sum и current_sum

            max_sum = max(max_sum, current_sum)

            current_sum = arr[i]

   

    return max(max_sum, current_sum)

   
# драйверная программа

def main():

    arr = [1, 2, 2, 4]

    n = len(arr)

   

    print("Maximum sum : " , maxsum_SIS(arr , n)),

  

if __name__ == '__main__':

    main()

      
# Этот код предоставлен 29AjayKumar

C #

// C # программа для поиска максимальной суммы строго
// увеличение подмассивов

using System; 

public class GFG{

  
// Возвращает максимальную сумму строго возрастающего
// подмассивы

    static int maxsum_SIS(int []arr, int n) { 

        // Инициализируем max_sum быть 0

        int max_sum = 0; 

  

        // Инициализируем текущую сумму как arr [0]

        int current_sum = arr[0]; 

  

        // Обход элементов массива после первого элемента.

        for (int i = 1; i < n; i++) { 

            // обновляем current_sum для строго увеличивающегося подмассива

            if (arr[i - 1] < arr[i]) { 

                current_sum = current_sum + arr[i]; 

            } else // строго увеличивающийся разрыв подмассива

            

                // обновляем max_sum и current_sum;

                max_sum = Math.Max(max_sum, current_sum); 

                current_sum = arr[i]; 

            

        

  

        return Math.Max(max_sum, current_sum); 

    

  
// драйверная программа

    public static void Main() { 

        int []arr = {1, 2, 2, 4}; 

        int n = arr.Length; 

        Console.WriteLine("Maximum sum : " + maxsum_SIS(arr, n)); 

    

  

  
// Этот код предоставлен 29AjayKumar

PHP

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

  
// Возвращает максимальную сумму строго
// увеличение подмассивов

function maxsum_SIS($arr , $n)

{

    // Инициализируем max_sum быть 0

    $max_sum = 0;

  

    // Инициализируем текущую сумму как arr [0]

    $current_sum = $arr[0];

  

    // Обход элементов массива после

    // первый элемент.

    for ($i = 1; $i < $n ; $i++)

    {

        // обновляем current_sum для строго

        // увеличение подмассива

        if ($arr[$i - 1] < $arr[$i])

            $current_sum = $current_sum + $arr[$i];

  

        else // строго увеличивается

             // разрыв подрешетки

        {

            // обновляем max_sum и current_sum;

            $max_sum = max($max_sum, $current_sum);

            $current_sum = $arr[$i];

        }

    }

  

    return max($max_sum, $current_sum);

}

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

$arr = array(1, 2, 2, 4);

$n = sizeof($arr);

  

echo "Maximum sum : "

      maxsum_SIS($arr , $n);

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


Выход:

Maximum sum : 6

Временная сложность: O (n)
Вспомогательное пространство: O (1)

Эта статья предоставлена Nishant_Singh (Pintu) . Если вы как GeeksforGeeks и хотели бы внести свой вклад, вы также можете написать статью с помощью contribute.geeksforgeeks.org или по почте статьи contribute@geeksforgeeks.org. Смотрите свою статью, появляющуюся на главной странице GeeksforGeeks, и помогите другим вундеркиндам.

Пожалуйста, пишите комментарии, если вы обнаружите что-то неправильное или вы хотите поделиться дополнительной информацией по обсуждаемой выше теме.

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

Найти максимальную сумму строго увеличивающегося подмассива

0.00 (0%) 0 votes