最长子序列

最长子序列

• C++语言编写 数组中有负数才有意义

1. 分治法

• 采用分治方法，最大子数组的位置在中点左边，中点右边和在跨越中点。由此将整个数据求累积和分成三段，分别计算累计和。
• 若最大子数组在段中，那么最大子数组在段的位置为中点左边，右边和跨越中点处，因此可以采用迭代算法。
• 若在其他段同段处理。
• 时间复杂度：设处理整个数组时间复杂度位T(n)
• 当处理最大子数组的位置在中点左/右边时将数组分为两部分，处理这部分时时间复杂度为2*T(N/2)
• 当处理最大子数组跨越中点时，即将左右边扫描一遍，即该部分时间复杂度为c*N
• T(n)=2T(N/2)+cN
  =2[2T(N/2^2)+cN/2]+cN
  =…(重复k-1次)
  =2^kO(1)+ckN (取最大)
  =O(NlogN)
  //将 T(n)=2T(N/2)+cN 带入T(N/2) 直到找到一个k，使得N/2^k=1

//首先计算出跨越中点的段的最大值即左右下标。
//跨越中点
void FindMaxCrossingSubarray(int A[], int low, int mid, int high, int &left, int &right, int &max)
{
	int left_sum = A[mid];  //目前找到的最大值
	int sum = 0; //所有值的和
	int max_left = mid; //左边坐标
	for (int i = mid; i >= low; --i)
	{
		sum += A[i];
		if (sum > left_sum)
		{
			left_sum = sum;
			max_left = i;
		}
	}

	int right_sum = 0;  //目前找到的最大值
	sum = 0; //所有值的和
	int max_right = mid; //右边坐标

	for (int i = mid + 1; i <= high; ++i)
	{
		sum += A[i];
		if (sum > right_sum)
		{
			right_sum = sum;
			max_right = i;
		}
	}
	left = max_left;
	right = max_right;
	max = left_sum + right_sum;
}

//整个数组：
void FindMaximumSubarray(int A[], int low, int high, int &left, int &right, int &max)
{
	if (high == low)
	{
		left = low; right = high; max = A[low];
		return;
	}
	else
	{
		int left_low, left_high, left_sum;  //坐标和最大累积和
		int right_low, right_high, right_sum;
		int cross_low, cross_high, cross_sum;

		int mid = (low + high) / 2;
		FindMaximumSubarray(A, low, mid, left_low, left_high, left_sum);
		FindMaximumSubarray(A, mid + 1, high, right_low, right_high, right_sum);
		FindMaxCrossingSubarray(A, low, mid, high, cross_low, cross_high, cross_sum);
		if (left_sum >= right_sum && left_sum >= cross_sum) {
			left = left_low; right = left_high; max = left_sum;
		}
		else if (right_sum >= left_sum && right_sum >= cross_sum)
		{
			left = right_low; right = right_high; max = right_sum;
		}
		else
		{
			left = cross_low; right = cross_high; max = cross_sum;
		}
	}
}

2. 在线处理法

• 复杂度T(N)=O(N)

int OnlineProcessing(int A[], int N,int& start,int& end)//数组个数 开始索引 结束索引
{
	int ThisSum, MaxSum;
	int i;
	start = end = -1;
	int tmp_start = 0;
	ThisSum = 0;
	MaxSum = -1;
	for (i = 0; i < N; i++)
	{
		ThisSum += A[i];//向右累加
		if (ThisSum > MaxSum) {
			start = tmp_start;
			end = i;//
			MaxSum = ThisSum;//发现更大的和则更新当前结果
		}
		else if (ThisSum < 0)//若当前子列和为负
		{
			tmp_start =  i + 1;
			ThisSum = 0;//则不可能使得后面的部分和增大，抛弃
		}
	}
	start=start<0?0:start;
	end=end<0?0:N-1;
	return MaxSum<0?0:MaxSum;
}