Los arreglos son una estructura básica de datos y una de las primeras que se conocen al empezar a programar.

Descripción

Dado un vector de N enteros, para cada índice i, se debe determinar el número de sub arreglos contiguos que cumplen las siguientes condiciones:

El valor en el índice i debe ser el elemento máximo en los sub arreglos contiguos, y
estos sub arreglos contiguos deben comenzar o terminar en el índice i.

Si el arreglo arr es una lista no vacía de enteros únicos que oscilan entre 1 y 1,000,000,000, y el tamaño N está entre 1 y 1,000,000, la salida esperada debe ser un arreglo donde cada índice i contiene un número entero que denota el número máximo de sub arreglos contiguos de arr[i].

Por ejemplo:
arr = [3, 4, 1, 6, 2] salida = [1, 3, 1, 5, 1]

Explicación:

Para el índice 0, [3] es el único sub arreglo contiguo que comienza (o termina) con 3, y el valor máximo en este sub arreglo es 3.
Para el índice 1, los posibles sub arreglos son [4], [3, 4], [4, 1].
Para el índice 2, sólo [1] es el único sub arreglo.
Para el índice 3, se tiene [6], [6, 2], [1, 6], [4, 1, 6], y [3, 4, 1, 6].
Para el índice 4, sólo [2].

Por tanto, la respuesta para la entrada [3, 4, 1, 6, 2] es [1, 3, 1, 5, 1].

Código

import math

def count_subarrays(arr):
  counter = [1] * len(arr)
  for i in range(len(arr)):
    max=arr[i]
    for h in range(i-1,-1,-1):
      if arr[h]<=max:
        counter[i] += 1
      else:
        break
        
    for j in range(i+1, len(arr)):
      if arr[j]<=max:
        counter[i] += 1
      else:
        break

  return counter

def printInteger(n):
  print('[', n, ']', sep='', end='')

def printIntegerList(array):
  size = len(array)
  print('[', end='')
  for i in range(size):
    if i != 0:
      print(', ', end='')
    print(array[i], end='')
  print(']', end='')

test_case_number = 1

def check(expected, output):
  global test_case_number
  expected_size = len(expected)
  output_size = len(output)
  result = True
  if expected_size != output_size:
    result = False
  for i in range(min(expected_size, output_size)):
    result &= (output[i] == expected[i])
  rightTick = '\u2713'
  wrongTick = '\u2717'
  if result:
    print(rightTick, 'Test #', test_case_number, sep='')
  else:
    print(wrongTick, 'Test #', test_case_number, ': Expected ', sep='', end='')
    printIntegerList(expected)
    print(' Your output: ', end='')
    printIntegerList(output)
    print()
  test_case_number += 1

if __name__ == "__main__":
  test_1 = [3, 4, 1, 6, 2]
  expected_1 = [1, 3, 1, 5, 1]
  output_1 = count_subarrays(test_1)
  check(expected_1, output_1)
  
  test_2 = [2, 4, 7, 1, 5, 3]
  expected_2 = [1, 2, 6, 1, 3, 1]
  output_2 = count_subarrays(test_2)
  check(expected_2, output_2)
  
  # This is a negative case
  test_3 = [1, 1, 7, 6, 8, 0]
  expected_3 = [2, 2, 4, 1, 2, 1]
  output_3 = count_subarrays(test_3)
  check(expected_3, output_3)
  
  # And this is the correct one
  test_4 = [1, 1, 7, 6, 8, 0]
  expected_4 = [2, 2, 4, 1, 6, 1]
  output_4 = count_subarrays(test_4)
  check(expected_4, output_4)

Creación: 2021.11.16
Última actualización: 2021.11.16

El contenido de este sitio puede ser copiado y reproducido libremente mientras no sea alterado y se cite su origen. Marcas y productos registrados son citados por referencia y sin fines de lucro o dolo. Todas las opiniones son a título personal del o los autores de éstas y, salvo sea expresado de otro modo, deben considerarse como registro y expresión de la experiencia de uso de aquello que es tratado. Para conocer más sobre la posición de privacidad y responsabilidad de lo que se presenta en este sitio web y como ha sido obtenido, consulte la declaración al respecto.