Dada una array de enteros. Una subsecuencia de arr[] se llama bitónica si primero es creciente y luego decreciente.
Ejemplos:
Input : arr[] = {1, 15, 51, 45, 33,
100, 12, 18, 9}
Output : 194
Explanation : Bi-tonic Sub-sequence are :
{1, 51, 9} or {1, 51, 100, 18, 9} or
{1, 15, 51, 100, 18, 9} or
{1, 15, 45, 100, 12, 9} or
{1, 15, 45, 100, 18, 9} .. so on
Maximum sum Bi-tonic sub-sequence is 1 + 15 +
51 + 100 + 18 + 9 = 194
Input : arr[] = {80, 60, 30, 40, 20, 10}
Output : 210
Este problema es una variación del problema estándar de la subsecuencia creciente más larga (LIS) y la subsecuencia bitónica más larga .
Construimos dos arreglos MSIBS[] y MSDBS[]. MSIBS[i] almacena la suma de la subsecuencia creciente que termina en arr[i]. MSDBS[i] almacena la suma de la subsecuencia Decreciente a partir de arr[i]. Finalmente, necesitamos devolver la suma máxima de MSIBS[i] + MSDBS[i] – Arr[i].
A continuación se muestra la implementación de la idea anterior.
C++
// C++ program to find maximum sum of bi-tonic sub-sequence
#include <bits/stdc++.h>
using namespace std;
// Function return maximum sum of Bi-tonic sub-sequence
int MaxSumBS(int arr[], int n)
{
int max_sum = INT_MIN;
// MSIBS[i] ==> Maximum sum Increasing Bi-tonic
// subsequence ending with arr[i]
// MSDBS[i] ==> Maximum sum Decreasing Bi-tonic
// subsequence starting with arr[i]
// Initialize MSDBS and MSIBS values as arr[i] for
// all indexes
int MSIBS[n], MSDBS[n];
for (int i = 0; i < n; i++) {
MSDBS[i] = arr[i];
MSIBS[i] = arr[i];
}
// Compute MSIBS values from left to right */
for (int i = 1; i < n; i++)
for (int j = 0; j < i; j++)
if (arr[i] > arr[j] && MSIBS[i] < MSIBS[j] + arr[i])
MSIBS[i] = MSIBS[j] + arr[i];
// Compute MSDBS values from right to left
for (int i = n - 2; i >= 0; i--)
for (int j = n - 1; j > i; j--)
if (arr[i] > arr[j] && MSDBS[i] < MSDBS[j] + arr[i])
MSDBS[i] = MSDBS[j] + arr[i];
// Find the maximum value of MSIBS[i] + MSDBS[i] - arr[i]
for (int i = 0; i < n; i++)
max_sum = max(max_sum, (MSDBS[i] + MSIBS[i] - arr[i]));
// return max sum of bi-tonic sub-sequence
return max_sum;
}
// Driver program
int main()
{
int arr[] = { 1, 15, 51, 45, 33, 100, 12, 18, 9 };
int n = sizeof(arr) / sizeof(arr[0]);
cout << "Maximum Sum : " << MaxSumBS(arr, n);
return 0;
}
Java
// java program to find maximum
// sum of bi-tonic sub-sequence
import java.io.*;
class GFG {
// Function return maximum sum
// of Bi-tonic sub-sequence
static int MaxSumBS(int arr[], int n)
{
int max_sum = Integer.MIN_VALUE;
// MSIBS[i] ==> Maximum sum Increasing Bi-tonic
// subsequence ending with arr[i]
// MSDBS[i] ==> Maximum sum Decreasing Bi-tonic
// subsequence starting with arr[i]
// Initialize MSDBS and MSIBS values as arr[i] for
// all indexes
int MSIBS[] = new int[n];
int MSDBS[] = new int[n];
for (int i = 0; i < n; i++) {
MSDBS[i] = arr[i];
MSIBS[i] = arr[i];
}
// Compute MSIBS values from left to right */
for (int i = 1; i < n; i++)
for (int j = 0; j < i; j++)
if (arr[i] > arr[j] && MSIBS[i] < MSIBS[j] + arr[i])
MSIBS[i] = MSIBS[j] + arr[i];
// Compute MSDBS values from right to left
for (int i = n - 2; i >= 0; i--)
for (int j = n - 1; j > i; j--)
if (arr[i] > arr[j] && MSDBS[i] < MSDBS[j] + arr[i])
MSDBS[i] = MSDBS[j] + arr[i];
// Find the maximum value of MSIBS[i] +
// MSDBS[i] - arr[i]
for (int i = 0; i < n; i++)
max_sum = Math.max(max_sum, (MSDBS[i] + MSIBS[i] - arr[i]));
// return max sum of bi-tonic
// sub-sequence
return max_sum;
}
// Driver program
public static void main(String[] args)
{
int arr[] = { 1, 15, 51, 45, 33, 100, 12, 18, 9 };
int n = arr.length;
System.out.println("Maximum Sum : " + MaxSumBS(arr, n));
}
}
// This code is contributed by vt_m
Python3
# Dynamic Programming implementation of maximum sum of bitonic subsequence
# Function return maximum sum of Bi-tonic sub-sequence
def max_sum(arr, n):
# MSIBS[i] ==> Maximum sum Increasing Bi-tonic
# subsequence ending with arr[i]
# MSDBS[i] ==> Maximum sum Decreasing Bi-tonic
# subsequence starting with arr[i]
# allocate memory for MSIBS and initialize it to arr[i] for
# all indexes
MSIBS = arr[:]
# Compute MSIBS values from left to right
for i in range(n):
for j in range(0, i):
if arr[i] > arr[j] and MSIBS[i] < MSIBS[j] + arr[i]:
MSIBS[i] = MSIBS[j] + arr[i]
# allocate memory for MSDBS and initialize it to arr[i] for
# all indexes
MSDBS = arr[:]
# Compute MSDBS values from right to left
for i in range(1, n + 1):
for j in range(1, i):
if arr[-i] > arr[-j] and MSDBS[-i] < MSDBS[-j] + arr[-i]:
MSDBS[-i] = MSDBS[-j] + arr[-i]
max_sum = float("-Inf")
# Find the maximum value of MSIBS[i] + MSDBS[i] - arr[i]
for i, j, k in zip(MSIBS, MSDBS, arr):
max_sum = max(max_sum, i + j - k)
# return max sum of bi-tonic sub-sequence
return max_sum
# Driver program to test the above function
def main():
arr = [1, 15, 51, 45, 33, 100, 12, 18, 9]
n = len(arr)
print (max_sum(arr, n))
if __name__ == '__main__':
main()
# This code is contributed by Neelam Yadav
C#
// C# program to find maximum
// sun of bi-tonic sub-sequence
using System;
class GFG {
// Function return maximum sum
// of Bi-tonic sub-sequence
static int MaxSumBS(int[] arr, int n)
{
int max_sum = int.MinValue;
// MSIBS[i] ==> Maximum sum Increasing Bi-tonic
// subsequence ending with arr[i]
// MSDBS[i] ==> Maximum sum Decreasing Bi-tonic
// subsequence starting with arr[i]
// Initialize MSDBS and MSIBS values as arr[i] for
// all indexes
int[] MSIBS = new int[n];
int[] MSDBS = new int[n];
for (int i = 0; i < n; i++) {
MSDBS[i] = arr[i];
MSIBS[i] = arr[i];
}
// Compute MSIBS values from left to right */
for (int i = 1; i < n; i++)
for (int j = 0; j < i; j++)
if (arr[i] > arr[j] && MSIBS[i] < MSIBS[j] + arr[i])
MSIBS[i] = MSIBS[j] + arr[i];
// Compute MSDBS values from right to left
for (int i = n - 2; i >= 0; i--)
for (int j = n - 1; j > i; j--)
if (arr[i] > arr[j] && MSDBS[i] < MSDBS[j] + arr[i])
MSDBS[i] = MSDBS[j] + arr[i];
// Find the maximum value of MSIBS[i] +
// MSDBS[i] - arr[i]
for (int i = 0; i < n; i++)
max_sum = Math.Max(max_sum, (MSDBS[i] + MSIBS[i] - arr[i]));
// return max sum of bi-tonic
// sub-sequence
return max_sum;
}
// Driver program
public static void Main()
{
int[] arr = { 1, 15, 51, 45, 33, 100, 12, 18, 9 };
int n = arr.Length;
Console.WriteLine("Maximum Sum : " + MaxSumBS(arr, n));
}
}
// This code is contributed by vt_m
PHP
<?php
// PHP program to find maximum
// sun of bi-tonic sub-sequence
function MaxSumBS($arr, $n)
{
$max_sum = PHP_INT_MIN;
// MSIBS[i] ==> Maximum sum Increasing
// Bi-tonic subsequence ending with arr[i]
// MSDBS[i] ==> Maximum sum Decreasing
// Bi-tonic subsequence starting with arr[i]
// Initialize MSDBS and MSIBS values
// as arr[i] for all indexes
$MSIBS = array();
$MSDBS = array();
for ($i = 0; $i < $n; $i++)
{
$MSDBS[$i] = $arr[$i];
$MSIBS[$i] = $arr[$i];
}
// Compute MSIBS values
// from left to right */
for ($i = 1; $i < $n; $i++)
for ($j = 0; $j < $i; $j++)
if ($arr[$i] > $arr[$j] &&
$MSIBS[$i] < $MSIBS[$j] +
$arr[$i])
$MSIBS[$i] = $MSIBS[$j] +
$arr[$i];
// Compute MSDBS values
// from right to left
for ($i = $n - 2; $i >= 0; $i--)
for ($j = $n - 1; $j > $i; $j--)
if ($arr[$i] > $arr[$j] &&
$MSDBS[$i] < $MSDBS[$j] +
$arr[$i])
$MSDBS[$i] = $MSDBS[$j] +
$arr[$i];
// Find the maximum value of
// MSIBS[i] + MSDBS[i] - arr[i]
for ($i = 0; $i < $n; $i++)
$max_sum = max($max_sum, ($MSDBS[$i] +
$MSIBS[$i] -
$arr[$i]));
// return max sum of
// bi-tonic sub-sequence
return $max_sum;
}
// Driver Code
$arr = array(1, 15, 51, 45, 33,
100, 12, 18, 9);
$n = count($arr);
echo "Maximum Sum : " ,
MaxSumBS($arr, $n);
// This code is contributed
// by shiv_bhakt.
?>
Javascript
<script>
// JavaScript program to find maximum
// sun of bi-tonic sub-sequence
// Function return maximum sum
// of Bi-tonic sub-sequence
function MaxSumBS(arr, n)
{
let max_sum = Number.MIN_VALUE;
// MSIBS[i] ==> Maximum sum Increasing Bi-tonic
// subsequence ending with arr[i]
// MSDBS[i] ==> Maximum sum Decreasing Bi-tonic
// subsequence starting with arr[i]
// Initialize MSDBS and MSIBS values as arr[i] for
// all indexes
let MSIBS = new Array(n);
let MSDBS = new Array(n);
for (let i = 0; i < n; i++) {
MSDBS[i] = arr[i];
MSIBS[i] = arr[i];
}
// Compute MSIBS values from left to right */
for (let i = 1; i < n; i++)
for (let j = 0; j < i; j++)
if (arr[i] > arr[j] &&
MSIBS[i] < MSIBS[j] + arr[i])
MSIBS[i] = MSIBS[j] + arr[i];
// Compute MSDBS values from right to left
for (let i = n - 2; i >= 0; i--)
for (let j = n - 1; j > i; j--)
if (arr[i] > arr[j] &&
MSDBS[i] < MSDBS[j] + arr[i])
MSDBS[i] = MSDBS[j] + arr[i];
// Find the maximum value of MSIBS[i] +
// MSDBS[i] - arr[i]
for (let i = 0; i < n; i++)
max_sum =
Math.max(max_sum, (MSDBS[i] + MSIBS[i] - arr[i]));
// return max sum of bi-tonic
// sub-sequence
return max_sum;
}
let arr = [ 1, 15, 51, 45, 33, 100, 12, 18, 9 ];
let n = arr.length;
document.write("Maximum Sum : " + MaxSumBS(arr, n));
</script>
Producción
Maximum Sum : 194
Complejidad del tiempo : O(n 2 )
Este artículo es una contribución de Nishant_Singh (Pintu) . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA