Encuentre la secuencia positiva de ejecución más larga en una array.
Ejemplos:
Input : arr[] = {1, 2, -3, 2, 3, 4, -6, 1,
2, 3, 4, 5, -8, 5, 6}
Output :Index : 7, length : 5
Input : arr[] = {-3, -6, -1, -3, -8}
Output : No positive sequence detected.
Una solución simple es usar dos bucles anidados. En el bucle exterior, buscamos elementos positivos. En el ciclo interno, contamos el número de positivos comenzando con el elemento positivo elegido por el ciclo externo. La complejidad temporal de esta solución es O(n^2).
Una solución eficiente es utilizar un solo bucle. Seguimos incrementando la cuenta mientras vemos números enteros positivos. Restablecemos la cuenta a 0 después de ver un negativo. Antes de reiniciar, verificamos si el conteo es mayor que el máximo.
C++
// CPP program to find longest running sequence
// of positive integers.
#include <bits/stdc++.h>
using namespace std;
// Prints longest sequence of positive integers in
// an array.
void getLongestSeq(int a[], int n)
{
// Variables to keep track of maximum length and
// starting point of maximum length. And same
// for current length.
int maxIdx = 0, maxLen = 0, currLen = 0, currIdx = 0;
for (int k = 0; k < n; k++) {
if (a[k] > 0) {
currLen++;
// New sequence, store
// beginning index.
if (currLen == 1)
currIdx = k;
}
else {
if (currLen > maxLen) {
maxLen = currLen;
maxIdx = currIdx;
}
currLen = 0;
}
}
if (maxLen > 0)
cout << "Length " << maxLen
<< ", starting index " << maxIdx << endl;
else
cout << "No positive sequence detected." << endl;
return;
}
// Driver code
int main()
{
int arr[] = { 1, 2, -3, 2, 3, 4, -6,
1, 2, 3, 4, 5, -8, 5, 6 };
int n = sizeof(arr) / sizeof(int);
getLongestSeq(arr, n);
return 0;
}
Java
// Java program to find longest running
// sequence of positive integers
import java.io.*;
class GFG {
// Prints longest sequence of
// positive integers in an array.
static void getLongestSeq(int a[], int n)
{
// Variables to keep track of maximum
// length and starting point of
// maximum length. And same for current
// length.
int maxIdx = 0, maxLen = 0, currLen = 0, currIdx = 0;
for (int k = 0; k < n; k++)
{
if (a[k] > 0)
{
currLen++;
// New sequence, store
// beginning index.
if (currLen == 1)
currIdx = k;
}
else
{
if (currLen > maxLen)
{
maxLen = currLen;
maxIdx = currIdx;
}
currLen = 0;
}
}
if (maxLen > 0)
{
System.out.print( "Length " + maxLen) ;
System.out.print( ",starting index " + maxIdx );
}
else
System.out.println("No positive sequence detected.") ;
return;
}
// Driver code
public static void main (String[] args)
{
int arr[] = { 1, 2, -3, 2, 3, 4, -6,
1, 2, 3, 4, 5, -8, 5, 6 };
int n = arr.length;
getLongestSeq(arr, n);
}
}
// This article is contributed by vt_m.
Python3
# Python code to find longest running
# sequence of positive integers.
def getLongestSeq(a, n):
maxIdx = 0
maxLen = 0
currLen = 0
currIdx = 0
for k in range(n):
if a[k] > 0:
currLen +=1
# New sequence, store
# beginning index.
if currLen == 1:
currIdx = k
else:
if currLen > maxLen:
maxLen = currLen
maxIdx = currIdx
currLen = 0
if maxLen > 0:
print('Index : ',maxIdx,',Length : ',maxLen,)
else:
print("No positive sequence detected.")
# Driver code
arr = [ 1, 2, -3, 2, 3, 4, -6,
1, 2, 3, 4, 5, -8, 5, 6]
n = len(arr)
getLongestSeq(arr, n)
# This code is contributed by "Abhishek Sharma 44"
C#
// C# program to find longest running
// sequence of positive integers.
using System;
class GFG {
// Prints longest sequence of
// positive integers in an array.
static void getLongestSeq(int []a, int n)
{
// Variables to keep track of maximum
// length and starting point of
// maximum length. And same for current
// length.
int maxIdx = 0, maxLen = 0, currLen = 0,
currIdx = 0;
for (int k = 0; k < n; k++)
{
if (a[k] > 0)
{
currLen++;
// New sequence, store
// beginning index.
if (currLen == 1)
currIdx = k;
}
else
{
if (currLen > maxLen)
{
maxLen = currLen;
maxIdx = currIdx;
}
currLen = 0;
}
}
if (maxLen > 0)
{
Console.Write( "Length " + maxLen) ;
Console.WriteLine( ",starting index "
+ maxIdx );
}
else
Console.WriteLine("No positive sequence"
+ " detected.") ;
return;
}
// driver code
public static void Main()
{
int []arr = { 1, 2, -3, 2, 3, 4, -6,
1, 2, 3, 4, 5, -8, 5, 6 };
int n = arr.Length;
getLongestSeq(arr, n);
}
}
// This code is contributed by Sam007
PHP
<?php
// PHP program to find longest running
// sequence of positive integers.
// Prints longest sequence of positive
// integers in an array.
function getLongestSeq($a, $n)
{
// Variables to keep track
// of maximum length and
// starting point of maximum
// length. And same for
// current length.
$maxIdx = 0;
$maxLen = 0;
$currLen = 0;
$currIdx = 0;
for ($k = 0; $k < $n; $k++) {
if ($a[$k] > 0) {
$currLen++;
// New sequence, store
// beginning index.
if ($currLen == 1)
$currIdx = $k;
}
else {
if ($currLen > $maxLen) {
$maxLen = $currLen;
$maxIdx = $currIdx;
}
$currLen = 0;
}
}
if ($maxLen > 0)
echo "Length " . $maxLen.
", starting index " .
$maxIdx ."\n" ;
else
echo "No positive sequence detected."."\n";
return;
}
// Driver Code
$arr = array(1, 2, -3, 2, 3, 4, -6,
1, 2, 3, 4, 5, -8, 5, 6);
$n = count($arr);
getLongestSeq($arr, $n);
// This code is contributed by Sam007
?>
Javascript
<script>
// Javascript program to find longest running
// sequence of positive integers.
// Prints longest sequence of
// positive integers in an array.
function getLongestSeq(a, n)
{
// Variables to keep track of maximum
// length and starting point of
// maximum length. And same for current
// length.
let maxIdx = 0, maxLen = 0, currLen = 0, currIdx = 0;
for (let k = 0; k < n; k++)
{
if (a[k] > 0)
{
currLen++;
// New sequence, store
// beginning index.
if (currLen == 1)
currIdx = k;
}
else
{
if (currLen > maxLen)
{
maxLen = currLen;
maxIdx = currIdx;
}
currLen = 0;
}
}
if (maxLen > 0)
{
document.write( "Length " + maxLen) ;
document.write( ", starting index "
+ maxIdx + "</br>");
}
else
document.write("No positive sequence"
+ " detected.") ;
return;
}
let arr = [ 1, 2, -3, 2, 3, 4, -6,
1, 2, 3, 4, 5, -8, 5, 6 ];
let n = arr.length;
getLongestSeq(arr, n);
</script>
Producción:
Length 5, starting index 7
El algoritmo es O(n) tiempo y O(1) espacio auxiliar.
Publicación traducida automáticamente
Artículo escrito por smarakchopdar y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA