问题描述:求最长递减子序列的长度
代码如下:
#include “string.h”
#include <iostream>
using namespace std;
void longest_decrease_sub(char *L, int size);
void longest_decrease_sub(char *L, int size)
{
char *d = new char[size];
char *p = new char[size];
d[size – 1] = 1;
for (int i = size – 1; i >= 0; i–)
{
int max = 0;
int index = 0;
for (int j = i; j<size; j++)
{
if (L[i]>L[j] && max <d[j])
{
max = d[j];
index = j;
}
}
if (max == 0)
{
d[i] = 1;
p[i] = -1;
}
else
{
d[i] = max + 1;
p[i] = index;
}
}
int max = 0;
int max_index = 0;
for (int i = 0; i<size; i++)
{
if (d[i]>max)
{
max = d[i];
max_index = i;
}
}
cout << (int)d[max_index] << endl;
delete[] d;
delete[] p;
}
int main()
{
int test_num = 0;
cin >> test_num;
for (int i = 0; i < test_num; i++)
{
char *p = new char;
cin >> p;
int n = strlen(p);
longest_decrease_sub(p, n);
}
return 0;
}
过学校judge网站过不了 报错如下:
Runtime Error:[ERROR] A Not allowed system call: runid:68977 callid:146
*** glibc detected *** ./Main: free(): invalid next size (normal): 0x092e2710 ***
代码如下:
#include “string.h”
#include <iostream>
using namespace std;
void longest_decrease_sub(char *L, int size);
void longest_decrease_sub(char *L, int size)
{
char *d = new char[size];
char *p = new char[size];
d[size – 1] = 1;
for (int i = size – 1; i >= 0; i–)
{
int max = 0;
int index = 0;
for (int j = i; j<size; j++)
{
if (L[i]>L[j] && max <d[j])
{
max = d[j];
index = j;
}
}
if (max == 0)
{
d[i] = 1;
p[i] = -1;
}
else
{
d[i] = max + 1;
p[i] = index;
}
}
int max = 0;
int max_index = 0;
for (int i = 0; i<size; i++)
{
if (d[i]>max)
{
max = d[i];
max_index = i;
}
}
cout << (int)d[max_index] << endl;
delete[] d;
delete[] p;
}
int main()
{
int test_num = 0;
cin >> test_num;
for (int i = 0; i < test_num; i++)
{
char *p = new char;
cin >> p;
int n = strlen(p);
longest_decrease_sub(p, n);
}
return 0;
}
过学校judge网站过不了 报错如下:
Runtime Error:[ERROR] A Not allowed system call: runid:68977 callid:146
*** glibc detected *** ./Main: free(): invalid next size (normal): 0x092e2710 ***
解决方案
40
char *p = new char;只分配一个字符,cin>>p的时候可能越界了