Рубрики

Подпоследовательность с максимальной нечетной суммой

Учитывая набор целых чисел, проверьте, существует ли подпоследовательность с нечетной суммой, и если да, то найдите максимальную нечетную сумму. Если ни одна подпоследовательность не содержит нечетную сумму, верните -1.

Примеры :

Input : arr[] = {2, 5, -4, 3, -1};
Output : 9
The subsequence with maximum odd 
sum is 2, 5, 3 and -1.

Input : arr[] = {4, -3, 3, -5}
Output : 7
The subsequence with maximum odd
sum is 4 and 3

Input :  arr[] = {2, 4, 6}
Output : -1
There is no subsequence with odd sum.

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

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

C ++

// C ++ программа для поиска максимальной суммы нечетных
// подпоследовательность, если она существует.
#include<bits/stdc++.h>

using namespace std;

  
// Возвращает максимальную сумму нечетной подпоследовательности, если существует
// Остальное возвращает -1

int findMaxOddSubarraySum(int arr[], int n)

{

    // Здесь min_odd - минимальное нечетное число (в

    // абсолютные условия). Инициализация с максимальным значением

    // из инт.

    int min_odd = INT_MAX;

  

    // Проверить, есть ли хотя бы одно нечетное число.

    bool isOdd = false;

  

    int sum = 0;  // Для хранения суммы всех положительных элементов

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

    {

        // Добавление положительного числа увеличит

        // сумма.

        if (arr[i] > 0)

            sum = sum + arr[i];

  

        // Найти минимальное нечетное число (абсолютное)

        // в массиве.

        if (arr[i]%2 != 0)

        {

            isOdd = true;

            if (min_odd> abs(arr[i]))

                min_odd = abs(arr[i]);

        }

    }

  

    // Если не было нечетного числа

    if (isOdd == false)

       return -1;

  

    // Теперь сумма будет нечетной или четной.

    // Если чёт, меняем его на нечётный. Как четное - нечетное = нечетное.

    // поскольку m - минимальное нечетное число (абсолютное).

    if (sum%2 == 0)

        sum = sum - min_odd;

  

    return sum;

}

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

int main()

{

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

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

    cout << findMaxOddSubarraySum(arr, n);

    return 0;

}

Джава

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

import java.io.*;

  

class GFG {

      
// Возвращает максимальную сумму нечетной подпоследовательности,
// если существует, иначе возвращается -1

static int findMaxOddSubarraySum(int arr[], int n)

{

    // Здесь min_odd - минимальное нечетное число

    // (в абсолютном выражении). Инициализация с

    // максимальное значение int.

    int min_odd = Integer.MAX_VALUE;

  

    // Чтобы проверить, есть ли минимум

    // одно нечетное число

    boolean isOdd = false;

      

    // Для хранения суммы всех положительных элементов

    int sum = 0

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

    {

        // Добавление положительного числа будет

        // увеличить сумму.

        if (arr[i] > 0)

            sum = sum + arr[i];

  

        // Найти минимальное нечетное число

        // (абсолют) в массиве.

        if (arr[i] % 2 != 0)

        {

            isOdd = true;

            if (min_odd > Math.abs(arr[i]))

                min_odd = Math.abs(arr[i]);

        }

    }

  

    // Если не было нечетного числа

    if (isOdd == false)

    return -1;

  

    // Теперь сумма будет нечетной или четной.

    // Если чёт, меняем его на нечётный.

    // Как четное - нечетное = нечетное.

    // так как м минимальное нечетное

    // число (абсолютное)

    if (sum % 2 == 0)

        sum = sum - min_odd;

  

    return sum;

}

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

public static void main (String[] args) 

{

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

    int n = arr.length;

    System.out.println(findMaxOddSubarraySum(arr, n));

          
}
}

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

python3

# Python программа для поиска
# максимальная сумма нечетных
# подпоследовательность, если она существует.

  
# Возвращает максимальную сумму нечетного
# подпоследовательность, если существует
# Остальное возвращает -1

def findMaxOddSubarraySum(arr, n):

  

    # Здесь min_odd является

    # минимальное нечетное число (в

    # абсолютные условия).

    # Инициализация с максимальным значением

    № инт.

    min_odd = +2147483647

   

    # Чтобы проверить, есть ли

    # хотя бы одно нечетное число

    isOdd = False

      

    # Для хранения суммы

    # все положительные элементы

    sum = 0  

    for i in range(n):

      

        # Добавление положительного числа

        # увеличится

        # сумма.

        if (arr[i] > 0):

            sum = sum + arr[i]

   

        # Чтобы найти минимум

        # нечетное число (абсолютное)

        # в массиве.

        if (arr[i]%2 != 0):

          

            isOdd = True

            if (min_odd > abs(arr[i])):

                min_odd = abs(arr[i])

   

    # Если не было нечетного числа

    if (isOdd == False):

         return -1

   

    # Теперь сумма будет

    # нечетное или четное.

    # Если даже, изменив его на

    # странный. Как четное - нечетное = нечетное.

    # так как м является минимумом

    # нечетное число (абсолютное).

    if (sum%2 == 0):

        sum = sum - m

   

    return sum

  

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

  

arr = [2, -3, 5, -1, 4]

n =len(arr)

  

print(findMaxOddSubarraySum(arr, n))

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

C #

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

using System;

  

class GFG {

      

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

    // если существует, иначе возвращается -1

    static int findMaxOddSubarraySum(int []arr, int n)

    {

          

        // Здесь min_odd - минимальное нечетное число

        // (в абсолютном выражении). Инициализация с

        // максимальное значение int.

        int min_odd = int.MaxValue;

      

        // Чтобы проверить, есть ли минимум

        // одно нечетное число

        bool isOdd = false;

          

        // Для хранения суммы всех положительных элементов

        int sum = 0; 

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

        {

              

            // Добавление положительного числа будет

            // увеличить сумму.

            if (arr[i] > 0)

                sum = sum + arr[i];

      

            // Найти минимальное нечетное число

            // (абсолют) в массиве.

            if (arr[i] % 2 != 0)

            {

                isOdd = true;

                if (min_odd > Math.Abs(arr[i]))

                    min_odd = Math.Abs(arr[i]);

            }

        }

      

        // Если не было нечетного числа

        if (isOdd == false)

            return -1;

      

        // Теперь сумма будет нечетной или четной.

        // Если чёт, меняем его на нечётный.

        // Как четное - нечетное = нечетное.

        // так как м минимальное нечетное

        // число (абсолютное)

        if (sum % 2 == 0)

            sum = sum - min_odd;

      

        return sum;

    }

      

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

    public static void Main () 

    {

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

        int n = arr.Length;

        Console.Write(findMaxOddSubarraySum(arr, n));

              

    }

}

  
// Этот код предоставлен нитин митталь.

PHP

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

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

function findMaxOddSubarraySum( $arr, $n)

{

    // Здесь min_odd - минимум

    // нечетное число (в абсолютном выражении).

    // Инициализация с максимальным значением

    // из инт.

    $min_odd = PHP_INT_MAX;

  

    // Чтобы проверить, есть ли

    // хотя бы одно нечетное число

    $isOdd = false;

  

    // Хранить сумму всего

    // положительные элементы

    $sum = 0; 

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

    {

        // Добавляем положительное число

        // увеличит сумму.

        if ($arr[$i] > 0)

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

  

        // Чтобы найти минимальное нечетное

        // число (абсолютное) в массиве.

        if ($arr[$i] % 2 != 0)

        {

            $isOdd = true;

            if ($min_odd > abs($arr[$i]))

                $min_odd = abs($arr[$i]);

        }

    }

  

    // Если не было нечетного числа

    if ($isOdd == false)

    return -1;

  

    // Теперь сумма будет либо

    // нечетное или четное. Если даже

    // меняем его на нечетный. В качестве,

    // четный - нечетный = нечетный. поскольку

    // м минимальное нечётное

    // число (абсолютное)

    if ($sum % 2 == 0)

        $sum = $sum - $min_odd;

  

    return $sum;

}

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

$arr = array(2, -3, 5, -1, 4);

$n = count($arr);

echo findMaxOddSubarraySum($arr, $n);

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

Выход :

11

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

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

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

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

Подпоследовательность с максимальной нечетной суммой

0.00 (0%) 0 votes