接着昨天的思考，汉诺塔问题递归。我思考最大子数组时候一直想着递归的思路是这样的： arr[0,…,start,…,end,…,temp,…,length) ————⬆——–⬆———|————– 通过维护start,end两个指针指向当前arr[0,temp)数组中的最大子数组 数组变为arr[0,temp+1)，则如果sum[end+1,…,temp+1)>0,则end = temp。 这样带来两个问题，一、start怎么确定（递推时候start是0呀？）？二、[end+1,…,temp+1)中有可能有比[start,…,end)数组大的数组，如图： 假如start、end在1区间，随着temp不断的向后移动、蓝色部分负数导致和小，会错误使得蓝1.黄2，蓝2，黄3的和比黄1小。这显然不是我想要的。
《剑指offer》书通过计算历遍数组的和currentSum，和一个表示目前子数组最大和的greatSum。如果currentSum>greatSum,那么更新greatSum。如果currentSum<0,那么currentSum = arr[temp]-(我的思路差在这里了)来判断更新。
求 x1 x 1 , x2 x 2 使得 ∫x2x1f(x)dx ∫ x 1 x 2 f ( x ) d x （x2>x1） （ x 2 > x 1 ） ,最大，积分上限函数，两个变量 求导呀，然后得到的点是正负号变化的时候的点是待选择的区间点？？然而并没有卵用8
∫x2x1f(x)dx ∫ x 1 x 2 f ( x ) d x （x2>x1），通过greatSum>0判断前面的子数组是否有累加的价值。并且不断的找函数 （ x 2 > x 1 ） ， 通 过 g r e a t S u m > 0 判 断 前 面 的 子 数 组 是 否 有 累 加 的 价 值 。 并 且 不 断 的 找 函 数
∫x2x1f(x)dx ∫ x 1 x 2 f ( x ) d x 的极小值值点。arr[i]<0,arr[i+1]>0,然后将x1，设置为最小值点的坐标，开始找极大值，然后和已经找到的最大值比较。（ 数学上通过求导来找极小值），这里一直在找可能的极小值（ 如果arr[i]<0,那么arr[i+1]可能极小值的起点）。—————-思路还是很混乱呀。。。。。 根据书上思路写的代码,书中 0x8000 0000 设置的很巧妙，当启动子。 [pStart、pEnd)为最大子数组。
int getMaxSubArr2(int **/*out*/ pStart, int **/*out*/pEnd, int * /*in*/arr, int /*in*/length,int &/*out*/sum) { if (arr == NULL || length <= 0) { return -1; } int *ppStart = arr; int *ppTempStart = arr; int *ppEnd = arr; int *ppTempEnd = arr; int greatSum = 0X80000000; int currentSum = 0; for (int i = 0; i < length; ++i) { if (currentSum < 0) { currentSum = arr[i]; ppTempStart = arr + i; ppTempEnd = ppTempStart + 1; } else { currentSum += arr[i]; ppTempEnd += 1; } if (currentSum > greatSum) { greatSum = currentSum; ppStart = ppTempStart; ppEnd = ppTempEnd; } } *pStart = ppStart; *pEnd = ppEnd; ppStart = NULL; ppEnd = NULL; ppTempEnd = NULL; ppTempStart = NULL; sum = greatSum; return 0; } int main() { //init(x, 10); //moveMethod(x, z, y,10); //cout << totalcount; int sum = 0; int arr[] = { 5, -4, -3, -9, 10, 8, 5, 9, 0, 1 }; int *pStart = NULL; int *pEnd = NULL; int c = getMaxSubArr2(&pStart, &pEnd, arr+3, 2, sum); for (auto ite = pStart; ite != pEnd; ite++) { cout << *ite<<","; } cout << endl; cout << c << endl; cout << sum << endl; system("pause"); return 0; }