一道算法题——符号平衡问题
最近在算法编程过程中碰到这样一个题目
给定n个整数a1,a2,an组成的序列。序列中元素a[i] 的符号定义为：
当a[i]> 0时，sgn(a[i])=1;当a[i]=0时,sgn(a[i])=0;当a[i] <0时sgn(a[i])=-1;
符号平衡问题要求给定序列的最长符号平衡段的长度L，即：
L=max{j-i+1},其中1= <i <=j <=n,而且是满足sgn(a[i])+sgn(a[i+1])+...+sgn(a[j])=0这个式子的所有的i,j组合中的最大值
例如，当n=10，相应序列为：1，1，-1，-2，0，1，3，-1，2，-1 时，L=9。
算法设计：
给定n个整数 a1,a2,an组成的序列，试设计一个O(n)时间算法，计算其最长符号
平衡段的长度。
数据输入：
由文件input.txt 提供输入数据。文件的第1 行是正整数n，第2行是整数序列a1,a2,an
结果输出:
将计算出的最长符号平衡段的长度输出到output.txt中。
输入文件示例 输出文件示例
input.txt output.txt
10 9
1 1 -1 -2 0 1 3 -1 2 -1
这个问题如果没有要求O(n)时间的话，我觉得不难，可是如果要做到O(n)的话，该怎么做呢，请各位高手指点小弟一下，小弟不甚感激
[解决办法]
下面的代码满足lz的要求，代码很简单，就不说明了：）
#include <stdio.h>
#include <assert.h>
#define sign(x) ((x) == 0 ? 0 : ((x) > 0 ? 1 : -1))
int calc (int data[], int cnt)
{
if (cnt <= 0)
return 0;
int * value = new int[cnt + 1];
int * first = new int[cnt + 1];
int * last = new int[cnt + 1];
for (int i = 0; i < cnt + 1; i++)
first[i] = -1;
/*
Initialize value, then value[i] represents the
sum of the first ith elements ' sign value.
*/
value[0] = 0;
for (int i = 1; i < cnt + 1; i++)
value[i] = value[i - 1] + sign(data[i - 1]);
/*
For each element v in value[0...cnt], first[v]
denotes the index of v 's first appearance, and
last[v] denotes the last appearance.
*/
for (int i = 0; i < cnt + 1; i++)
{
int v = value[i];
if (first[v] == -1)
first[v] = last[v] = i;
else
last[v] = i;
}
int max = 0;
for (int i = 0; i < cnt + 1; i++)
if (first[i] != -1 && max < last[i] - first[i])
max = last[i] - first[i];
delete value;
delete first;
delete last;
return max;
}
int main()
{
int data1[] = {1, 1, -1, -2, 0, 1, 3, -1, 2, -1};
int data2[] = {1};
int data3[] = {0};
int max1 = calc (data1, sizeof(data1) / sizeof(data1[0]));
int max2 = calc (data2, sizeof(data2) / sizeof(data2[0]));
int max3 = calc (data3, sizeof(data3) / sizeof(data3[0]));
assert (max1 == 9);
assert (max2 == 0);
assert (max3 == 1);
return 0;
}
[解决办法]
典型的利用空间换时间。
也可以先计算这个学列的符号和，假如是＋n，从序列两头开始跳过那些正数，如果跳过了n个，则剩下的刚好是符号平衡串，如果少于n个，而两个指针指向的都是非正数，则以此为头寻找平衡串，直到正的个数超过负的，再跳过正的，直到跳过的正数等于n，记录下最大的平衡串。不知道讲清楚了没有
[解决办法]
在fflush(stdin) 基础上修改bug后给出一个完善版本：
#include <stdio.h>
#include <assert.h>
#include "iostream.h "
#define sign(x) ((x) == 0 ? 0 : ((x) > 0 ? 1 : -1))
int calc (int data[], int cnt)
{
if (cnt <= 0)
return 0;
int * value = new int[cnt + 1];
int * first = new int[2*cnt + 1];
int * last = new int[2*cnt + 1];
int i = 0;
for ( i = 0; i < 2*cnt + 1; i++)
first[i] = -1;
/*
Initialize value, then value[i] represents the
sum of the first ith elements ' sign value.
*/
value[0] = 0;
for ( i = 1; i < cnt + 1; i++)
value[i] = value[i - 1] + sign(data[i - 1]);
/*
For each element v in value[0...cnt], first[v]
denotes the index of v 's first appearance, and
last[v] denotes the last appearance.
*/
for ( i = 0; i < cnt + 1; i++)
{
int v = value[i];
if (first[v+cnt] == -1)
first[v+cnt] = last[v+cnt] = i;
else
last[v+cnt] = i;
}
int max = 0;
for ( i = 0; i < 2*cnt + 1; i++)
{
if (first[i] != -1 && max < last[i] - first[i])
{
max = last[i] - first[i];
}
}
delete [] value;
delete [] first;
delete [] last;
return max;
}
int main()
{
int data1[] = {-1, -1, -1, -2, 0, 1, 3, 2};
int max1 = calc (data1, sizeof(data1) / sizeof(data1[0]));
cout < < "The max value is: " < <max1 < <endl;
return 0;
}
