Encuentre la suma máxima de longitudes de subarreglos que no se superponen (elementos contiguos) con k como el elemento máximo.
Ejemplos:
Input : arr[] = {2, 1, 4, 9, 2, 3, 8, 3, 4}
k = 4
Output : 5
{2, 1, 4} => Length = 3
{3, 4} => Length = 2
So, 3 + 2 = 5 is the answer
Input : arr[] = {1, 2, 3, 2, 3, 4, 1}
k = 4
Output : 7
{1, 2, 3, 2, 3, 4, 1} => Length = 7
Input : arr = {4, 5, 7, 1, 2, 9, 8, 4, 3, 1}
k = 4
Ans = 4
{4} => Length = 1
{4, 3, 1} => Length = 3
So, 1 + 3 = 4 is the answer
Fuente de la pregunta: https://www.geeksforgeeks.org/amazon-interview-experience-set-376-campus-internship/
Algoritmo:
Traverse the array starting from first element
Take a loop and keep on incrementing count
If element is less than equal to k
if array element is equal to k, then mark
a flag
If flag is marked, add this count to answer
Take another loop and traverse the array
till element is greater than k
return ans
Implementación:
C++
// CPP program to calculate max sum lengths of
// non overlapping contiguous subarrays with k as
// max element
#include <bits/stdc++.h>
using namespace std;
// Returns max sum of lengths with maximum element
// as k
int calculateMaxSumLength(int arr[], int n, int k)
{
int ans = 0; // final sum of lengths
// number of elements in current subarray
int count = 0;
// variable for checking if k appeared in subarray
int flag = 0;
for (int i = 0; i < n;) {
count = 0;
flag = 0;
// count the number of elements which are
// less than equal to k
while (arr[i] <= k && i < n) {
count++;
if (arr[i] == k)
flag = 1;
i++;
}
// if current element appeared in current
// subarray add count to sumLength
if (flag == 1)
ans += count;
// skip the array elements which are
// greater than k
while (arr[i] > k && i < n)
i++;
}
return ans;
}
// driver program
int main()
{
int arr[] = { 4, 5, 7, 1, 2, 9, 8, 4, 3, 1 };
int size = sizeof(arr) / sizeof(arr[0]);
int k = 4;
int ans = calculateMaxSumLength(arr, size, k);
cout << "Max Length :: " << ans << endl;
return 0;
}
Java
// A Java program to calculate max sum lengths of
// non overlapping contiguous subarrays with k as
// max element
public class GFG
{
// Returns max sum of lengths with maximum element
// as k
static int calculateMaxSumLength(int arr[], int n, int k) {
int ans = 0; // final sum of lengths
// number of elements in current subarray
int count = 0;
// variable for checking if k appeared in subarray
int flag = 0;
for (int i = 0; i < n;) {
count = 0;
flag = 0;
// count the number of elements which are
// less than equal to k
while (i < n && arr[i] <= k) {
count++;
if (arr[i] == k)
flag = 1;
i++;
}
// if current element appeared in current
// subarray add count to sumLength
if (flag == 1)
ans += count;
// skip the array elements which are
// greater than k
while (i < n && arr[i] > k)
i++;
}
return ans;
}
// driver program to test above method
public static void main(String[] args) {
int arr[] = { 4, 5, 7, 1, 2, 9, 8, 4, 3, 1 };
int size = arr.length;
int k = 4;
int ans = calculateMaxSumLength(arr, size, k);
System.out.println("Max Length :: " + ans);
}
}
// This code is contributed by Sumit Ghosh
Python3
# Python program to calculate max sum lengths of non
# overlapping contiguous subarrays with k as max element
# Returns max sum of lengths with max elements as k
def calculateMaxSumLength(arr, n, k):
ans = 0 # final sum of lengths
i=0
while i < n :
# number of elements in current sub array
count = 0
# Variable for checking if k appeared in the sub array
flag = 0
# Count the number of elements which are
# less than or equal to k
while i < n and arr[i] <= k :
count = count + 1
if arr[i] == k:
flag = 1
i = i + 1
# if current element appeared in current
# subarray and count to sumLength
if flag == 1:
ans = ans + count
# skip the array elements which are greater than k
while i < n and arr[i] > k :
i = i + 1
return ans
# Driver Program
arr = [4, 5, 7, 1, 2, 9, 8, 4, 3, 1]
size = len(arr)
k = 4
ans = calculateMaxSumLength(arr, size, k)
print ("Max Length ::",ans)
# Contributed by Rohit
C#
// A C# program to calculate max
// sum lengths of non overlapping
// contiguous subarrays with k as
// max element
using System;
class GFG {
// Returns max sum of lengths
// with maximum element as k
static int calculateMaxSumLength(int []arr,
int n,
int k)
{
// final sum of lengths
int ans = 0;
// number of elements in
// current subarray
int count = 0;
// variable for checking if
// k appeared in subarray
int flag = 0;
for(int i = 0; i < n;)
{
count = 0;
flag = 0;
// count the number of
// elements which are
// less than equal to k
while (i < n && arr[i] <= k)
{
count++;
if (arr[i] == k)
flag = 1;
i++;
}
// if current element
// appeared in current
// subarray add count
// to sumLength
if (flag == 1)
ans += count;
// skip the array
// elements which are
// greater than k
while (i < n && arr[i] > k)
i++;
}
return ans;
}
// Driver Code
public static void Main()
{
int []arr = {4, 5, 7, 1, 2, 9, 8, 4, 3, 1};
int size = arr.Length;
int k = 4;
int ans = calculateMaxSumLength(arr, size, k);
Console.WriteLine("Max Length :: " + ans);
}
}
// This code is contributed by anuj_67.
PHP
<?php
// PHP program to calculate max sum lengths
// of non overlapping contiguous subarrays
// with k as max element
// Returns max sum of lengths with maximum
// element as k
function calculateMaxSumLength(&$arr, $n, $k)
{
$ans = 0; // final sum of lengths
// number of elements in current subarray
$count = 0;
// variable for checking if k
// appeared in subarray
$flag = 0;
for ($i = 0; $i < $n😉
{
$count = 0;
$flag = 0;
// count the number of elements which
// are less than equal to k
while ($arr[$i] <= $k && $i < $n)
{
$count++;
if ($arr[$i] == $k)
$flag = 1;
$i++;
}
// if current element appeared in current
// subarray add count to sumLength
if ($flag == 1)
$ans += $count;
// skip the array elements which are
// greater than k
while ($arr[$i] > $k && $i < $n)
$i++;
}
return $ans;
}
// Driver Code
$arr = array( 4, 5, 7, 1, 2,
9, 8, 4, 3, 1 );
$size = sizeof($arr);
$k = 4;
$ans = calculateMaxSumLength($arr, $size, $k);
echo "Max Length :: " . $ans . "\n";
// This code is contributed by ita_c
?>
Javascript
<script>
// A Javascript program to calculate max sum lengths of
// non overlapping contiguous subarrays with k as
// max element
// Returns max sum of lengths with maximum element
// as k
function calculateMaxSumLength(arr,n,k)
{
let ans = 0; // final sum of lengths
// number of elements in current subarray
let count = 0;
// variable for checking if k appeared in subarray
let flag = 0;
for (let i = 0; i < n;) {
count = 0;
flag = 0;
// count the number of elements which are
// less than equal to k
while (i < n && arr[i] <= k) {
count++;
if (arr[i] == k)
flag = 1;
i++;
}
// if current element appeared in current
// subarray add count to sumLength
if (flag == 1)
ans += count;
// skip the array elements which are
// greater than k
while (i < n && arr[i] > k)
i++;
}
return ans;
}
// driver program to test above method
let arr=[4, 5, 7, 1, 2, 9, 8, 4, 3, 1];
let size = arr.length;
let k = 4;
let ans = calculateMaxSumLength(arr, size, k);
document.write("Max Length :: " + ans);
//This code is contributed by avanitrachhadiya2155
</script>
Producción
Max Length::4
Complejidad de tiempo : O(n)
Puede parecer O(n2), pero si observa más de cerca, la array se recorre solo una vez
Otro enfoque:
Algoritmo:
Traverse the array from first element to last element
if the element is less than k increment the count
if the element is equals to k
if k is not found
increment the count and mark flag as 1
if k is found
add the value of count to ans and mark count as 1
if the element is greater than k
if k is present in the subarray add the value of count to ans and
assign value of count and flag variables as 0
finally check again if k value is found in subarray or not
if k is found return sum of answer and count
if not return ans
Implementación:
C++
// C++ program to find Maximum sum of lengths of
// non-overlapping subarrays with k as the max element.
#include <bits/stdc++.h>
using namespace std;
// Below function calculates the Maximum sum of lengths of
// non-overlapping subarrays with k as the max element.
int calculateMaxSumLength(int arr[], int n, int k)
{
// maximum sum of lengths
int ans = 0;
// number of elements in current subarray
int count = 0;
// flag variable for checking if k is present
// in current subarray or not
int flag = 0;
for (int i = 0; i < n; i++) {
// increment the count if element in arr is less
// than k
if (arr[i] < k) {
count++;
}
// if the element is equals to k
else if (arr[i] == k) {
if (flag == 0) {
count++;
flag = 1;
}
// if flag is 1, we can say k is already present
// in that subarray. So, add the value of count
// to ans variable and make the count value as 1
// because we found the k
else {
ans += count;
count = 1;
}
}
// if element in arr is greater than k
else {
// if k is present in the subarray
// add the value of count to ans variable
if (flag == 1) {
ans += count;
}
// assign value of count and flag variables as 0
count = 0;
flag = 0;
}
}
// Check again if k value is found in subarray
// if k is found, return sum of values of variables ans
// and count if k is not found, return value of variable
// ans.
if (flag == 1) {
return ans + count;
}
return ans;
}
// driver program
int main()
{
int arr[] = { 4, 5, 7, 1, 2, 9, 8, 4, 3, 1 };
int size = sizeof(arr) / sizeof(arr[0]);
int k = 4;
int ans = calculateMaxSumLength(arr, size, k);
cout << "Max Length :: " << ans << endl;
return 0;
}
// Contributed by Ravi Teja Kuchipudi
Java
// JAVA program to find Maximum sum of lengths of
// non-overlapping subarrays with k as the max element.
class GFG {
// Below function calculates the Maximum sum of lengths
// of non-overlapping subarrays with k as the max
// element.
static int calculateMaxSumLength(int arr[], int n,
int k)
{
// maximum sum of lengths
int ans = 0;
// number of elements in current subarray
int count = 0;
// flag variable for checking if k is present
// in current subarray or not
int flag = 0;
for (int i = 0; i < n; i++) {
// increment the count if element in arr is less
// than k
if (arr[i] < k) {
count++;
}
// if the element is equals to k
else if (arr[i] == k) {
// if flag is equals to 0 then make flag
// variable value as 1 and increment the
// count.
if (flag == 0) {
count++;
flag = 1;
}
// if flag is 1, we can say k is already
// present in that subarray. So, add the
// value of count to ans variable and make
// the count value as 1 because we found the
// k
else {
ans += count;
count = 1;
}
}
// if element in arr is greater than k
else {
// if k is present in the subarray
// add the value of count to ans variable
if (flag == 1) {
ans += count;
}
// assign value of count and flag variables
// as 0
count = 0;
flag = 0;
}
}
// Check again if k value is found in subarray
// if k is found, return sum of values of variables
// ans and count if k is not found, return value of
// variable ans.
if (flag == 1) {
return ans + count;
}
return ans;
}
// driver program to test above method
public static void main(String[] args)
{
int arr[] = { 4, 5, 7, 1, 2, 9, 8, 4, 3, 1 };
int size = arr.length;
int k = 4;
int ans = calculateMaxSumLength(arr, size, k);
System.out.println("Max Length :: " + ans);
}
}
// Contributed by Ravi Teja Kuchipudi
Python3
# program to find Maximum sum of lengths of
# non-overlapping subarrays with k as the max element.
def calculateMaxSumLength(arr, n, k):
# maximum sum of lengths
ans = 0
# number of elements in current subarray
count = 0
# flag variable for checking if k is present in current subarray or not
flag = 0
for i in range(n):
# increment the count if element in arr is less than k
if arr[i] < k:
count = count+1
# if the element is equals to k
elif arr[i] == k:
# if flag is equals to 0 then make flag variable value as 1 and
# increment the count.
if flag == 0:
count = count + 1
flag = 1
# if flag is 1, we can say k is already present in that subarray.
# So, add the value of count to ans variable and
# make the count value as 1 because we found the k
else:
ans = ans + count
count = 1
# if element in arr is greater than k
else:
# if k is present in the subarray
# add the value of count to ans variable
if flag == 1:
ans = ans + count
# assign value of count and flag variables as 0
count = 0
flag = 0
# Check again if k value is found in subarray
# if k is found, return sum of values of variables ans and count
# if k is not found, return value of variable ans.
if flag == 1:
return ans + count
return ans
# Driver Program
arr = [4, 5, 7, 1, 2, 9, 8, 4, 3, 1]
size = len(arr)
k = 4
ans = calculateMaxSumLength(arr, size, k)
print("Max Length ::", ans)
# Contributed by Ravi Teja Kuchipudi
C#
// C# program to find Maximum sum of lengths of
// non-overlapping subarrays with k as the max element.
using System;
class GFG
{
// Returns max sum of lengths
// with maximum element as k
static int calculateMaxSumLength(int[] arr, int n, int k)
{
// maximum sum of lengths
int ans = 0;
// number of elements in current subarray
int count = 0;
// flag variable for checking if k is present
// in current subarray or not
int flag = 0;
for (int i = 0; i < n; i++)
{
// increment the count if element in arr is less
// than k
if (arr[i] < k)
{
count++;
}
// if the element is equals to k
else if (arr[i] == k)
{
// if flag is equals to 0 then make flag
// variable value as 1 and increment the
// count.
if (flag == 0)
{
count++;
flag = 1;
}
// if flag is 1, we can say k is already
// present in that subarray. So, add the
// value of count to ans variable and make
// the count value as 1 because we found the
// k
else
{
ans += count;
count = 1;
}
}
// if element in arr is greater than k
else
{
// if k is present in the subarray
// add the value of count to ans variable
if (flag == 1)
{
ans += count;
}
// assign value of count and flag variables
// as 0
count = 0;
flag = 0;
}
}
// Check again if k value is found in subarray
// if k is found, return sum of values of variables
// ans and count if k is not found, return value of
// variable ans.
if (flag == 1)
{
return ans + count;
}
return ans;
}
// Driver Code
public static void Main()
{
int []arr = {4, 5, 7, 1, 2, 9, 8, 4, 3, 1};
int size = arr.Length;
int k = 4;
int ans = calculateMaxSumLength(arr, size, k);
Console.WriteLine("Max Length :: " + ans);
}
}
// This code is contributed by kothavvsaakash
Javascript
<script>
// JavaScript program to find Maximum sum of lengths of
// non-overlapping subarrays with k as the max element.
// Below function calculates the Maximum sum of lengths of
// non-overlapping subarrays with k as the max element.
function calculateMaxSumLength(arr, n, k)
{
// maximum sum of lengths
let ans = 0;
// number of elements in current subarray
let count = 0;
// flag variable for checking if k is present
// in current subarray or not
let flag = 0;
for (let i = 0; i < n; i++)
{
// increment the count if element in arr is less
// than k
if (arr[i] < k) {
count++;
}
// if the element is equals to k
else if (arr[i] == k) {
if (flag == 0) {
count++;
flag = 1;
}
// if flag is 1, we can say k is already present
// in that subarray. So, add the value of count
// to ans variable and make the count value as 1
// because we found the k
else {
ans += count;
count = 1;
}
}
// if element in arr is greater than k
else
{
// if k is present in the subarray
// add the value of count to ans variable
if (flag == 1)
{
ans += count;
}
// assign value of count and flag variables as 0
count = 0;
flag = 0;
}
}
// Check again if k value is found in subarray
// if k is found, return sum of values of variables ans
// and count if k is not found, return value of variable
// ans.
if (flag == 1) {
return ans + count;
}
return ans;
}
// driver program
let arr = [ 4, 5, 7, 1, 2, 9, 8, 4, 3, 1 ];
let size = arr.length;
let k = 4;
let ans = calculateMaxSumLength(arr, size, k);
document.write("Max Length :: ",ans,"</br>");
// This code is contributed by shinjanpatra
</script>
Producción
Max Length::4
Complejidad de tiempo : O(n)
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