数据结构与算法面试题：子数组的最大和

问题分析

在数组的每一个位置处保存当前的最大值，当前的最大值组成为：

f ( x i ) = \begin{cases} x_i & \text{ if } i=0\; or\; f\left ( x_{i-1} \right )\leqslant 0 \\ f\left ( x_{i-1} \right )+x_i & \text{ if } f\left ( x_{i-1} \right )> 0 \end{cases} 

解决方案

int get_max_subarray(int *a, int length, bool &is_array_ok){ if (NULL == a || length <= 0){ is_array_ok = false; return 0; } int *p_h_a = (int *)malloc(sizeof(int) * length); // 遍历数组 int max_num = 0; for (int i = 0; i < length; i++){ if (i == 0 || (i > 0 && p_h_a[i-1] <= 0)){ p_h_a[i] = a[i]; }else{ p_h_a[i] = p_h_a[i-1] + a[i]; } if (max_num < p_h_a[i]) max_num = p_h_a[i]; } free(p_h_a); is_array_ok = true; return max_num; }