最小正子段和

问题

问题链接：最小正子段和 时间限制：1秒 空间限制：131072KB

Input

N个整数组成的序列a[1],a[2],a[3],…,a[n]，从中选出一个连续的子序列（a[i],a[i+1],…a[j]），使这个子序列的和>0，并且这个和是所有和>0的子序列中最小的。

例如：4，-1，5，-2，-1，2，6，-2。-1，5，-2，-1，序列和为1，是最小的。

OutPut

第1行：整数序列的长度N（2 <= N <= 50000) 第2 - N+1行：N个整数

Input示例

8, 4, -1, 5, -2, -1, 2, 6, -2

Output示例

1

动态规划

这个问题与“最大子段和”有些相似，但是如果想尝试用动态规划去做的话并不容易。先给出我想到的动态规划方法，再来讨论它的性能。

一个比较容易想到的定义状态的方式是：用dp[i]表示前i个元素的最小正子段和，如何求dp[i+1]？第(i+1)个元素又和前面i个元素构成了i个连续的子序列，意味着求dp[i+1]还得求所有以a[i+1]结尾的连续子序列的最小正子段和，选择最小的再和dp[i]比较，然后取二者较小的作为dp[i+1]的值。

可见，按照这种定义方式，在从状态dp[i]转移到状态dp[i+1]时又出现了新的问题：如何求以a[i+1]结尾的所有连续子序列的最小正子段和，即需要求下面各个序列的最小正子段和：

a[i],a[i+1] a[i-1],a[i],a[i+1] … a[2],…,a[i+1]

其实最终目的是求{a[2],…,a[i+1]}的最小正子段和（这个问题具有最优子结构）但是在求序列{a[2],a[3],…,a[i+1]}的最小正子段和时，不但需要知道{a[3],a[4],…,a[i+1]}的最小正子段和，还需要知道所有以a[2]开头的连续子序列的最小正子段和，即需要求下面序列的最小正子段和：

a[2] a[2],a[3] … a[2],a[3],…,a[i]

看来需要考虑新的状态定义方式。

定义dp[i][j]表示以a[i]开始，以a[j]结束的连续子序列的最小正子段和。

状态转移：dp[i][j] = min{dp[i][j-1], dp[i+1][j]} 边界条件：dp[i][i] = a[i](while a[i] > 0), dp[i][i] = 0(while a[i] < 0)(0的含义是不存在最小正子段和)

自底向上进行递推的代码：

for(int t = 2; t <= n; ++t) {
	for(j = t; j <= n; ++j) {
		i = j - t + 1;
		if(dp[i][j-1] > 0 && dp[i+1][j] > 0)
			dp[i][j] = min(dp[i][j-1], dp[i+1][j]);
		else if(dp[i][j-1] > 0 && dp[i+1][j] < 0)
			dp[i][j] = dp[i][j-1];
		else if(dp[i][j-1] < 0 && dp[i+1][j] > 0)
			dp[i][j] = dp[i+1][j];
		else
			dp[i][j] = 0;
	}
}

上面代码源于这样的递推方案：

S1. 初始化dp[1][1], dp[2][2], ... , dp[n][n]（当a[i]>0,dp[i][i]=a[i]，否则dp[i][i] = 0）; S2. 计算dp[1][2], dp[2][3], ... , dp[n-1][n]； S3. 计算dp[1][3], dp[2][4], ... , dp[n-2][n]； … S(n-1). 计算dp[1][n-1], dp[2][n]； Sn. 计算dp[1][n]。

按序求出序列长度分别为1，2，… ，n的连续子序列的最小正子段和。

上面方法的时间复杂度是$O(\frac{n(n-1)}{2})$，对于数组规模不大的问题完全可以在很短的时间内解决，但是本问题中设定数组的长度最大可以到50000，对于1秒的时间限制还是不够的。所以，需要寻找更低时间复杂度的算法。

更好的方法：贪心策略

记sum[i]表示前i个元素的累和。 步骤一：计算sum数组（求sum[1], sum[2], … , sum[n]）； 步骤二：对sum数组从小到大排序，排序时保留元素在原数组中的索引； 步骤三： 　　3.1 找出sum数组中最小的正元素； 　　3.2 计算出排序后的sum数组所有相邻两个元素的差sum[i+1]-sum[i]，并且只当sum[i+1]在原数组中的索引大于sum[i]时才作差。 步骤四：步骤三求出来的所有值应该都是非负的，取其中最小的正数，作为最终的结果，即最小正子段和。

如对序列4, -1, 5, -2, -1进行上面的操作： 步骤一：sum = 4, 3, 8, 6, 5 步骤二：sum = 3(2), 4(1), 5(5), 6(4), 8(3) （括号里的数字表示元素在原数组中的索引/下标） 步骤三： 　　3.1 3 　　3.2 1 （来自于5-4） 步骤四：最小正子段和为1

贪心的正确性

上面的算法为什么是有效的呢？在于它只关注所有的和为正的子序列。上面的步骤二和步骤三其实就是求所有的和为正数的连续子序列。它是用了这样的思想：求区间[i,j]的连续子序列的和可以用区间[1,j]的连续子序列的和减去区间[1,i-1]的连续子序列的和。如何保证和为正呢？对所有以1开始的区间的连续子序列的和从小到大排个序，后面减去前面的一定非负。但要排除不可行的情况，即如果用区间[1,k]的连续子序列和减去区间[1,j]的连续子序列和，必须保证k > j，这就是为什么要在排序时保留索引（下标）的原因。而只在相邻两个元素之间作差则避免了很多不必要的计算。

算法分析

从上面给出的步骤不难看出，整个算法的效率取决于步骤二，即排序。而这一步我们通常能够以$O(n\log{n})$的时间复杂度完成，所以这种方法比动态规划效率更高。

代码（C++）

#include <cstdio>
#include <algorithm>

using namespace std;

struct node
{
	long long sum;	// 累和
	int id;			// 在原数组中的索引
}data[50001];

// 定义排序规则
bool cmp(node x, node y)
{
	if(x.sum != y.sum)
		return x.sum < y.sum;
	return x.id < y.id;
}

int main()
{
	int n;
	int i, a;
	long long ans=50001;
	
	scanf("%d", &n);
	data[0].sum = 0; data[0].id = 0;
	// 步骤一：计算sum数组，O(n)
	for(i = 1; i <= n; ++i) {
		scanf("%d", &a);
		data[i].sum = data[i-1].sum + a;
		data[i].id = i;
	}
	// 步骤二：排序，O(n*log(n))
	sort(data+1, data+n+1, cmp);
	// 步骤3.1：找出sum数组中的最小正元素，O(n)
	for(i = 1; i <= n; ++i) {
		if(data[i].sum > 0) {
			ans = data[i].sum;
			break;
		}
	}
	// 步骤3.2：计算出排序后的sum数组所有**相邻**两个元素的差，O(n)
	for(i = 2; i <= n; ++i) {
		if(data[i].sum == data[i-1].sum)
			continue;
		else
			if(data[i].id > data[i-1].id)
				ans = min(ans, data[i].sum-data[i-1].sum);
	}
	// 步骤四
	if(ans == 50001) ans = 0;
	printf("%lld\n", ans);

	return 0;
}