算法学习笔记最大子数组问题

题目&＃xff1a;给定义数组A&＃xff0c;长度为n&＃xff0c;找出数组A中的最大子数组&＃xff0c;例如数组A&＃61;{-23,18,20,-7,12}&＃xff0c;则最大子数组为{18,20,-7,12}。

解题思路&＃xff1a;

  ①很容易想到的方案是简单地尝试每对可能的组合&＃xff0c;然后从这些组合中找出最大的子数组。从数组中选择一个数A(i)&＃xff0c;然后计算以A(i)开始的所有子数组的和&＃xff0c;计算的次数为(n-i)&＃xff0c;选择的次数为n&＃xff0c;因此该算法的时间复杂度为Θ(n^2)&＃xff0c;该算法不可取。

  ②使用分治策略来求解。假设要寻找数组A[low,high]的最大子数组&＃xff0c;将数组分为规模相同的两部分&＃xff0c;中间的位置假设为mid。数组A所有的连续子数组A[i..j]所处的位置必然是以下三种情况之一&＃xff1a;

      a. 完全位于子数组A[low,mid]中&＃xff0c;因此low≤i≤j≤mid

      b.完全位于子数组A[mid&＃43;1,high]中&＃xff0c;因此mid&＃43;1≤i≤j≤high

       c.跨越了中间元素&＃xff0c;因此low≤i≤mid

  因此数组A的最大子数组所处的位置必然是这三种情况的一种。参考归并排序中递归思想&＃xff0c;递归地求解A[low,mid]和A[mid&＃43;1,high]中的最大子数组&＃xff0c;然后计算跨越中间元素的最大子数组&＃xff0c;剩下的问题就是找出这三个最大子数组中的最大子数组。

  代码实现如下&＃xff1a;

#include
#include #ifndef INT_MIN
#define INT_MIN (-((int)(~0U>>1)) - 1)
#endifstruct subarray {int start;int end;int sum;
};void find_max_cross_subarray(int *a, int low, int mid, int high, void *p)
{struct subarray *sa &＃61; (typeof(sa))p;int max_left, max_right;int left_sum, right_sum;int sum;int i;left_sum &＃61; INT_MIN;sum &＃61; 0;for (i &＃61; mid; i >&＃61; low; --i) {sum &＃43;&＃61; a[i];if (sum > left_sum) {max_left &＃61; i;left_sum &＃61; sum;}}right_sum &＃61; INT_MIN;sum &＃61; 0;for (i &＃61; mid &＃43; 1; i <&＃61; high; &＃43;&＃43;i) {sum &＃43;&＃61; a[i];if (sum > right_sum) {max_right &＃61; i;right_sum &＃61; sum;}}sa->start &＃61; max_left;sa->end &＃61; max_right;sa->sum &＃61; left_sum &＃43; right_sum;
}void find_max_subarray(int *a, int low, int high, void *p)
{struct subarray *sa &＃61; (typeof(sa))p;struct subarray *left_sa, __left_sa;struct subarray *right_sa, __right_sa;struct subarray *cross_sa, __cross_sa;struct subarray *tmp;int mid &＃61; (low &＃43; high) / 2;if (low > high) {fprintf(stderr, "Invalid argument.\n");return;}memset(sa, 0, sizeof(*sa));if (high &＃61;&＃61; low) {sa->sum &＃61; a[low];sa->start &＃61; sa->end &＃61; low;return;}left_sa &＃61; &__left_sa;right_sa &＃61; &__right_sa;cross_sa &＃61; &__cross_sa;find_max_subarray(a, low, mid, left_sa);find_max_subarray(a, mid &＃43; 1, high, right_sa);find_max_cross_subarray(a, low, mid, high, cross_sa);if ((left_sa->sum >&＃61; right_sa->sum) &&(left_sa->sum >&＃61; cross_sa->sum)) {tmp &＃61; left_sa;} else if ((right_sa->sum >&＃61; left_sa->sum) && (right_sa->sum >&＃61; cross_sa->sum)) {tmp &＃61; right_sa;} else {tmp &＃61; cross_sa;}memcpy(sa, tmp, sizeof(*sa));
}int main(void)
{int source[] &＃61; {13, -3, -25, 20, -3, -16, -23, 18, 20, -7, 12, -5, -22, 15, -4, 7};struct subarray sa;find_max_subarray(source, 0, sizeof(source) / sizeof(source[0]) - 1, &sa);printf("Max sum: %d, start: %d, end: %d.\n", sa.sum, sa.start, sa.end);return 0;
}

  ③《算法导论》中提出的一个解题思路&＃xff0c;从数组的左边界开始&＃xff0c;由左至右处理&＃xff0c;记录到目前为止已经处理过的最大子数组。若已知A[1..j]的最大子数组基于如下性质将解扩展为A[1..j&＃43;1]的最大子数组&＃xff1a;A[1..j&＃43;1]的最大子数组要么是A[1..j]的最大子数组&＃xff0c;要么是某个子数组A[i..j&＃43;1]&＃xff08;1≤i≤j&＃43;1)。在已知A[1..j]的最大子数组的情况下&＃xff0c;可以在线性时间内找出形如A[i..j&＃43;1]的最大子数组。该算法的时间复杂度为因此该算法的时间复杂度为Θ(n)。

  代码实现如下所示&＃xff1a;

#include
#include struct subarray {int start;int end;int sum;
};#define max(__x, __y) ((__x) > (__y) ? (__x) : (__y))static void max_sumarray(int *a, int len, void *p)
{struct subarray *sa &＃61; (typeof(sa))p;int i;int max_sum, prev, tmp;int start, end;if (!sa || (len <&＃61; 0)) {fprintf(stderr, "Invalid argument.\n");return;}memset(sa, 0, sizeof(*sa));max_sum &＃61; a[0];prev &＃61; a[0];start &＃61; end &＃61; 0;for (i &＃61; 1; i start &＃61; sa->end &＃61; i;} else {sa->start &＃61; start;sa->end &＃61; i;}}sa->sum &＃61; max_sum;
}int main(void)
{int source[] &＃61; {13, -3, -25, 20, -3, -16, -23, 18, 20, -7, 12, -5, -22, 15, -4, 7};struct subarray sa;max_sumarray(source, sizeof(source) / sizeof(source[0]), &sa);printf("Max sum: %d, start: %d, end: %d.\n", sa.sum, sa.start, sa.end);return 0;
}