算法导论 课后作业4.1-5
4.1-5使用线性时间开销的算法得出最大子数组
先做如下规定：
数组下标从1开始
当说A[i,j]的值时，指该子数组中所有元素的和
题目:
思路:
题目中给出的思路属于动态规划，使用已经计算出的结果辅助接下来的计算
如题目所述，若已知A[1,j]中的最大子数组，A[1,j+1]中的最大子数组要么为A[1,j]中的最大子数组，要么为A[i,j+1]的最大值
如果A[1,j+1]中最大子数组为A[i,j+1]的最大值,确定i值时对所有的i可能取值(1<=i<=j+1)进行比较，这将花费O(n),使算法时间复杂度为O(n^2),但在动态规划中，在已知A[1,j]中的形如A[i,j]的子数组的最大值的i取值时，可以在O(1)时间得出A[i,j+1]取最大值时i的取值，使算法时间复杂度为O(n)
以下是对在已知A[1,j]中,A[i,j]最大时i取值时求A[1,j+1]中A[i,j+1]的分析
已知A[1,j]中,A[i,j]的最大值在i=k时取得
对于A[1,j+1]中A[i,j+1]，在从j+1 向1 遍历i的值时可想象这样一个过程，不断有元素被添加到A[i,j+1]这个数组里来，要对每个A[i,j+1]的值进行比较
A[i,j+1]的结果将有两种,加入A[j],不加入A[j],
如果不加入A[j]那么i的取值为j+1；
如果加入A[j],那么其必须加入整个A[k,j],因为A[k,j]是A[1,j]中A[i,j]的最大子数组，加入其他数组的结果都小于加入A[k,j];
综上，我们寻找的A[1,j+1]中的最大子数组，既A[1,j]中最大子数组,A[j+1],A[k,j]+A[j+1],三个数组中的最大数组
数学表达:
先定义:
msA[1,j]=find_max_subarray(A[1,j])
迭代式:
A[1,j+1]=max(msA[1,j],A[j+1],A[k,j]+A[j+1])
c++实现:
#include<iostream>
struct FindMaxSubarrayReturn {
int begin;
int len;
int sum;
};
class FindMaxSubarray
{
public:
FindMaxSubarrayReturn find_max_subarray_non_recursion(int* v, int begin, int len);
void test_non_recursion();
};
FindMaxSubarrayReturn FindMaxSubarray::find_max_subarray_non_recursion(int* v, int begin, int len)
{
int k = 0;
int right = 0;
int left = 0;
int sum1=v[begin];//for msA[1,j]
int sum2 = v[begin];//for msA[k,j]
for (int i = 1; i < begin + len; i++) {
if (sum1 >= v[i] &&sum1>=v[i]+sum2) {
}
else if (v[i] >= sum1 && v[i] >= sum2 + v[i]) {
left = i;
right = i;
sum1 = v[i];
}
else {
left = k;
right = i;
sum1 = sum2 + v[i];
}
if (v[i] >= sum2 + v[i]) {
k = i;
sum2 = v[i];
}
else {
sum2 += v[i];
}
}
FindMaxSubarrayReturn ret;
ret.begin = left;
ret.len = right - left +1;
ret.sum = sum1;
return ret;
}
void FindMaxSubarray::test_non_recursion()
{
int v[] = { 13,-3,-25,20,-3,-16,-23,18,20,-7,12,-5,-22,15,-4,7 };
FindMaxSubarrayReturn ret;
ret = find_max_subarray_non_recursion(v, 0, 16);
std::cout << "result: " << std::endl;
std::cout << "length: " << ret.len << std::endl;
for (int i = 0; i < ret.len; i++) {
std::cout << v[i + ret.begin];
std::cout << " ";
}
std::cout << std::endl;
std::cout <<"sum: "<< ret.sum << std::endl;
}
int main(int argc,char* argv[]) {
FindMaxSubarray find_max_subarray;
find_max_subarray.test_non_recursion();
return 0;
}
