连续最大字段和与最大字段积

求数组中满足给定和的数对

给定两个有序整型数组a和b，各有n个元素，求两个数组中满足给定和的数对，即对a中元素i和b中元素j，，满足i + j = d(d已知)

分析

两个指针i和j分别指向数组的首尾，然后从两端同时向中间遍历，直到两个指针交叉。

代码

FixedSum(int* a, int* b, int n, int d){for (int i = 0, j = n – 1; i < n && j >= 0){if (a[i] + b[j] < d)++i ;else if (a[i] + b[j] == d){cout << a[i] << << b[j] << endl ;++i ;–j ;}–j ;}}

最大子段和

给定一个整型数组a，求出最大连续子段之和，如果和为负数，则按0计算，比如1， 2， -5， 6， 8则输出6 + 8 = 14

分析

编程珠玑上的经典题目，不多说了。

代码

Sum(int* a, int n){int curSum = 0;int maxSum = 0;for (int i = 0; i < n; i++){if (curSum + a[i] < 0)curSum = 0;else{curSum += a[i] ;maxSum = max(maxSum, curSum);}}return maxSum;}

最大子段积

给定一个整型数组a，求出最大连续子段的乘积，比如 1， 2， -8， 12， 7则输出12 * 7 = 84

分析

与最大子段和类似，注意处理负数的情况

代码

MaxProduct(int *a, int n){minProduct = r = (int i = 0; i < n; i++){if (a[i] > 0){maxProduct *= a[i];minProduct = min(minProduct * a[i], 1);}else if (a[i] == 0){maxProduct = 1;minProduct = 1;}{int temp = maxProduct;maxProduct = max(minProduct * a[i], 1);minProduct = temp * a[i];}r = max(r, maxProduct);}return r;}

家!甜蜜的家!天下最美好的莫过於家