Spoj zwraca limit time extended {c#}

Question

zadanie Arraysub  zwraca mi time limit exceeded a   jak poprwawić pogram by nie zwracał błedu 

using System;
using System.Linq;

namespace ConsoleApp17
{
    internal class Program
    {
        private static void Main(string[] args)
        {
            int n = Convert.ToInt32((Console.ReadLine()));

            int k;

            int val = 0;

            int[] arr = Console.ReadLine().Split(' ', StringSplitOptions.RemoveEmptyEntries).Select(int.Parse).ToArray();
            k = Convert.ToInt32((Console.ReadLine()));

            for (int i = 0; i < n - k + 1; i++)
            {
                val = arr[i];
                for (int j = i; j < i + k; j++)
                {
                    if (val < arr[j])
                    {
                        val = arr[j];
                    }
                }

                Console.Write(val + " ");
            }
        }
    }
}

 

Answer 1

Twój algorytm działa teraz w złożoności O(nk), więc to zdecydowanie za wolno. Możesz spróbować rozwiązać to szybciej korzystając z seta albo kolejki monotonicznej.

Comments

coś takiego pomoże czy nie

            C(9,new int[]{1,2,3,1,4,5,2,3,6},3);
        

        private static void C(int n, int[] arr, int k)

        {
            int val = 0;
            for (int i = 0; i < n - k + 1; i++)
            {
                val = arr[i];
                for (int j = i; j < i + k; j++)
                {
                    if (val < arr[j])
                    {
                        val = arr[j];
                    }
                }

                Console.Write(val + " ");
            }
        }

 

---

Niestety nie. To wciąż jest O(nk)

---

@Whistleroosh podeślesz jakiś example bym wiedział o co chodzi

---

Musisz albo skorzystać ze struktury danych set. Która jest już nawet zaimplementowana w c#. Albo z kolejki monotonicznej

---

@Whistleroosh dobrze myslę 

     HashSet<int> oddNumbers = new HashSet<int>(n);

i później

for oddnumver,add

i

array copy

 

---

Nie bardzo rozumiem o co chodzi w drugiej i trzeciej linijce. Ale uświadomiłem sobie, że źle Ci powiedziałem, musisz przecież trzymać wielokrotne wystąpienia tej samej liczby, więc nie możesz korzystać z seta a musisz skorzystać z multiseta