寻找最大平衡子阵的空间有效算法？

#包括&lt；iostream&gt；
#定义M 15
使用名称空间std；
void getSum（int arr[]，int prefixsum[]，int size）{
int i；
前缀sum[0]=arr[0]=0；
前缀sum[1]=arr[1]；
对于（i=2；i&lt；=size；i++）{
前缀sum[i]=前缀sum[i-1]+arr[i]；
}
}
无效查找（int a[]，int&amp；start，int&amp；end）{
while（开始&lt；结束）{
int mid=（开始+结束）/2；
如果（（结束-开始+1）==2*（a[结束]-a[开始-1]））
打破
如果（（结束-开始+1）&gt；2*（a[结束]-a[开始-1]））{
如果（a[开始]==0和a[结束]==1）
开始++；否则
结束--；
}否则{
如果（a[开始]==1和a[结束]==0）
开始++；否则
结束--；
}
}
}
int main（）{
整数大小，arr[M]，ps[M]，开始=1，结束，宽度；
;
cin&gt；&gt；尺寸；
arr[0]=0；
结束=大小；
对于（int i=1；i&lt；=size；i++）
cin&gt；&gt；arr[i]；
getSum（arr、ps、size）；
查找（ps、开始、结束）；
如果（开始！=结束）
不能&lt；&lt；（开始-1）&lt；“（结束-1）&lt；&lt；&lt；&lt；结束；否则不能&lt；&lt；&lt；&lt；“无解决方案”；
返回0；
}

现在我的算法是O（n）时间和O（Dn）空间，其中Dn是列表中的总不平衡。

此解决方案不会修改列表

设D为列表中1和0的差值

首先，让我们线性地遍历列表并计算D，看看它是如何工作的：

我将以这个列表为例：l=1100111100001110

元素D
空0
1 1
1.2&lt-
0 1
0 0
1 1
1 2
1 3
1 4
0 3
0 2
0 1
0 0
1 1
1 2
1 3
0.2&lt-

找到最长的平衡子阵相当于在D中找到两个相等的元素，它们距离较远。（在本例中，2 2用箭头标记。）

最长的平衡子阵列位于元素+1的第一次出现和元素的最后一次出现之间。（第一个箭头+1和最后一个箭头：00111100001110）

备注：

最长的子阵列将始终位于D的两个元素之间
介于[0，Dn]之间，其中Dn是D的最后一个元素。（在
上一个示例）Dn是系统中1s和0s之间的总不平衡
列表（如果Dn为负，则为[Dn，0]

在这个例子中，这意味着我不需要“看”3s或4s

证明：

让Dn>0

如果存在由p（p>Dn）分隔的子数组。自0&lt；Dn&lt；P
在到达D的第一个元素，它等于P之前，我们到达一
元素等于Dn。因此，由于列表的最后一个元素等于Dn，因此由Dns分隔的子数组比由Ps分隔的子数组最长。因此，我们不需要查看Ps

由于相同的原因，p不能小于0

对于Dn&lt；0

现在让我们研究D，D不是随机的，两个连续元素之间的差总是1或-1。在D和初始列表之间有一个简单的双射。因此，对于这个问题，我有两种解决方案：

• 第一种方法是跟踪每个产品的第一次和最后一次出现
  D中介于0和Dn之间的元素（参见备注）
• 第二种方法是将列表转换为D，然后处理D

---

第一个解决方案

目前，我找不到比第一种更好的方法：

首先计算Dn（以O（n）为单位）。Dn=2

第二，不是创建D，而是创建一个字典，其中键是D的值（介于[0和Dn]之间），每个键的值是一对（a，b），其中a是键的第一次出现，b是最后一次出现

元素D词汇表
空0{0:（0,0）}
1 1 {0:(0,0) 1:(1,1)}
1 2 {0:(0,0) 1:(1,1) 2:(2,2)}
0 1 {0:(0,0) 1:(1,3) 2:(2,2)}
0 0 {0:(0,4) 1:(1,3) 2:(2,2)}
1 1 {0:(0,4) 1:(1,5) 2:(2,2)}
1 2 {0:(0,4) 1:(1,5) 2:(2,6)}
1 3 { 0:(0,4) 1:(1,5) 2:(2,6)}
1 4 {0:(0,4) 1:(1,5) 2:(2,6)}
0 3{0:(0,4) 1:(1,5) 2:(2,6) }
0 2 {0:(0,4) 1:(1,5) 2:(2,9) }
0 1 {0:(0,4) 1:(1,10) 2:(2,9) }
0 0 {0:(0,11) 1:(1,10) 2:(2,9) }
1 1 {0:(0,11) 1:(1,12) 2:(2,9) }
1 2 {0:(0,11) 1:(1,12) 2:(2,13)}
1 3 {0:(0,11) 1:(1,12) 2:(2,13)}
0 2 {0:(0,11) 1:(1,12) 2:(2,15)}

您选择了差异最大的元素：2:（2,15）并且是l[3:15]=00111100001110（l=1100111100001110）

时间复杂性：

2个过程，第一个用于计算Dn，第二个用于构建
措辞。
在字典里找到最大值

总数为0（n）

空间复杂性：

D:O（1）中的当前元素是词汇表O（Dn）

我不会因为这句话而把3和4放在毕业典礼上

复杂性是O（n）时间和O（Dn）空间（在平均情况下为Dn&lt；
n） .

我想，对于这种方法，可能有一种比用措辞更好的方法

欢迎提出任何建议

希望能有帮助

---

第二个解决方案（只是一个想法而不是真正的解决方案）

第二种方法是将您的列表转换为D（因为从D返回列表很容易）。（O（n）时间和O（1）空间，因为我就地变换列表，即使它可能不是“有效”的O（1））

然后从D开始，你需要找到2个相等的元素，它们距离我们越远

这看起来像是在链表中查找最长的循环，Richard Brent算法的修改可能会返回最长的循环，但我不知道如何执行，并且需要O（n）时间和O（1）空间

找到最长的周期后，返回第一个列表并打印它

该算法需要O（n）时间和O（1）空间复杂度