Нахождение палиндрома (TurboPascal)

[VladKB1]

Задан числовой массив a[n]. Найдите отрезок массива максимальной длины, в котором первое
число равно последнему, второе – предпоследнему и так далее.
Если подходящих отрезков несколько, выведите первый по порядку.

Формат ввода: первая строка: n. n ≤ 7000. Вторая строка: элементы массива.
-maxint ≤ a[i] ≤ maxint

Формат вывода: искомый отрезок.
input.txt
9
5 3 4 7 4 3 6 6 3
output.txt
3 4 7 4 3

Не проходит 14 тест по времени (1 тест = 1 секунда ,а у меня 85 сек (( )

var
 n,i,j,p,l,x,u: longint;
 q: boolean;
 a: array [1..7000] of longint;
begin
 assign(input,'input.txt');
 reset(input);
 assign(output,'output.txt');
 rewrite(output);

 read(n);
 for i:=1 to n do read(a[i]);

 for i:=1 to n do
 for j:=n downto i do
 begin
  q:=True;
  for u:=i to i+((j-i) div 2) do
  q:=q and (a[u]=a[j+i-u]);

  if q and (l<j-i+1) then
  begin
   l:=j-i+1;
   P:=i;
  end;
 end;
 for i:=p to p+l-2 do write(a[i],' ');
 writeln(a[p+l-1]);
end.

[BDA]

Массив сделать массивом integer и заменить

for u:=i to i+((j-i) div 2) do
q:=q and (a[u]=a[j+i-u]);

на

u := i;
tmp := i + ((j - i) div 2);
while q and (u <= tmp) do
begin
  q := a[u] = a[j + i - u];
  inc(u);
end;

Но не гарантирую, что это намного ускорит.

[SlavaSSU]

хахах. говорил же я, не пройдет по времени!)))
а вообще надо решать задачу за O(n^2);

короче вот на с++, там сам разберешься

int ansl, ansr;
int ans = 0;

for(int i = 1; i <= n; i++)
{
int cur = 1;
int l = i - 1, r = i + 1;
while(l >= 1 && r <= n && a[l] == a[r])
{
l--;
r++;
cur += 2;
}

if(cur > ans)
{
ans = cur;
ansl = ++l;
ansr = --r;
}
}

for(int i = 1; i <= n; i++)
{
int cur = 0;
int l = i - 1, r = i;
while(l >= 1 && r <= n && a[l] == a[r])
{
l--;
r++;
cur += 2;
}

if(cur > ans)
{
ans = cur;
ansl = ++l;
ansr = --r;
}
}

теперь в ansl и ansr хранятся границы макс подстроки палиндрома

[VladKB1]

Сообщение от BDA

Массив сделать массивом integer и заменить

for u:=i to i+((j-i) div 2) do
q:=q and (a[u]=a[j+i-u]);

на

u := i;
tmp := i + ((j - i) div 2);
while q and (u <= tmp) do
begin
  q := a[u] = a[j + i - u];
  inc(u);
end;

Но не гарантирую, что это намного ускорит.

а вот тут давать значение P и L ?

begin
  q := a[u] = a[j + i - u];
  inc(u);
end;

[BDA]

VladKB1, заменить в коде только 2 указанные строки (и тип элементов массива), а всё остальное оставить как есть. Да и способ SlavaSSU можно попробовать.

[VladKB1]

BDA Большое спасибо теперь оно за 2 сек проходит , но нужно за 1

А про Славин код я разобрался почти но не всё (не селён в С++ , то что подчеркнуто не знаю)

int ansl, ansr;
int ans = 0;

for(int i = 1; i <= n; i++)
{
int cur = 1;
int l = i - 1, r = i + 1;
while(l >= 1 && r <= n && a[l] == a[r])
{
l--;
r++;
cur += 2;
}

if(cur > ans)
{
ans = cur;
ansl = ++l;
ansr = --r;
}
}

[BDA]

i++ называется постинкрементом. Например:

i = 3;
k = i++;

Результат: k = 3, i = 4.
В данном случае переписывайте в обычный цикл for..to..do.
a[l] == a[r] - это оператор равенства (в паскале просто "=").
l--;r++;cur += 2; - расписываются похоже: l := l - 1; r := r + 1; cur := cur + 2;. Или можно воспользоваться процедурами inc и dec.
ansl = ++l; -> l := l + 1; ansl := l;, хотя в данном случае значение l уже неважно, так что можно ansl := l + 1;

[VladKB1]

Сообщение от BDA

i++ называется постинкрементом. Например:

i = 3;
k = i++;

Результат: k = 3, i = 4.
В данном случае переписывайте в обычный цикл for..to..do.
a[l] == a[r] - это оператор равенства (в паскале просто "=").
l--;r++;cur += 2; - расписываются похоже: l := l - 1; r := r + 1; cur := cur + 2;. Или можно воспользоваться процедурами inc и dec.
ansl = ++l; -> l := l + 1; ansl := l;, хотя в данном случае значение l уже неважно, так что можно ansl := l + 1;

Этот код не работает он не проходит все тесты

[SlavaSSU]

покажи весь код