C语言实现数组最大子段和及最接近0的子段和算法

求最大连续子向量和问题

给定一个包含正负数的整数向量，寻找一个连续子向量，使得其元素之和最大。例如对于向量 {31,-41,59,26,-53,58,97,-93,-23,84}，最大和为 187（对应子向量 59, 26, -53, 58, 97）。

第一：原始双重循环法

目的： 直观理解问题，验证后续算法的正确性。
入口： 遍历所有可能的起始和结束索引。
动作： 使用双层循环计算每个子向量的和，并记录最大值。
复杂度： O(n²)。虽然简单，但效率较低。

// 原始暴力解法
int original(int v[], int len) {
    int maxsofar = 0;
    for (int i = 0; i < len; i++) {
        int sum = 0;
        for (int j = i; j < len; j++) {
            sum += v[j];
            if (sum > maxsofar) {
                maxsofar = sum;
            }
        }
    }
    return maxsofar;
}

第二：前缀和优化法

目的： 减少重复计算，提升基础解法的速度。
入口： 预先计算数组的前缀和。
动作： 利用公式 sum(i, j) = prefix[j] - prefix[i-1] 快速得到子向量和，仍需遍历所有区间。
复杂度： O(n²)，常数项更小。

// 使用前缀和优化的暴力法
int original_ex(int v[], int len) {
    int *cumarr = malloc(len * sizeof(int));
    cumarr[0] = v[0];
    for (int i = 1; i < len; i++) {
        cumarr[i] = cumarr[i-1] + v[i];
    }
    
    int maxsofar = 0;
    for (int i = 0; i < len; i++) {
        for (int j = i; j < len; j++) {
            int sum = (i == 0) ? cumarr[j] : (cumarr[j] - cumarr[i-1]);
            if (sum > maxsofar) {
                maxsofar = sum;
            }
        }
    }
    free(cumarr);
    return maxsofar;
}

第三：分治算法

目的： 利用递归将问题规模减半，平衡左右与跨越中间三种情况。
入口： 定义数组的左右边界 low 和 high。
动作： 1. 计算左半部分的最大和。 2. 计算右半部分的最大和。 3. 计算跨越中点的最大和（需向左延伸找最大，向右延伸找最大）。 4. 三者取最大值作为当前区间的结果。

完成状态： 递归终止于单元素或空区间，返回累加的最大值。

// 分治法求解最大子段和
int divAndCon(int v[], int low, int high) {
    if (low > high) return 0;
    if (low == high) return (v[low] > 0) ? v[low] : 0;
    
    int mid = (low + high) / 2;
    
    // 求左半部分最大值
    int lmax = divAndCon(v, low, mid);
    // 求右半部分最大值
    int rmax = divAndCon(v, mid + 1, high);
    
    // 求跨越中点的最大值
    int l_sum = 0, left_max = 0;
    for (int i = mid; i >= low; i--) {
        l_sum += v[i];
        if (l_sum > left_max) left_max = l_sum;
    }
    
    int r_sum = 0, right_max = 0;
    for (int i = mid + 1; i <= high; i++) {
        r_sum += v[i];
        if (r_sum > right_max) right_max = r_sum;
    }
    
    int cross_max = left_max + right_max;
    
    // 返回三者最大值
    return (cross_max > lmax) ? ((cross_max > rmax) ? cross_max : rmax) : ((lmax > rmax) ? lmax : rmax);
}

第四：线性扫描法（Kadane's Algorithm）

目的： 以最优的时间复杂度解决问题。
入口： 单次遍历数组。
动作： 维护两个变量：max_ending_here 表示以当前元素结尾的最大子段和，若其为负则重置为0；max_so_far 记录全局最大值。

// 线性扫描法，时间复杂度 O(n)
int scan(int v[], int len) {
    int maxsofar = 0;
    int maxendinghere = 0;
    
    for (int i = 0; i < len; i++) {
        maxendinghere += v[i];
        if (maxendinghere < 0) {
            maxendinghere = 0;
        } else if (maxendinghere > maxsofar) {
            maxsofar = maxendinghere;
        }
    }
    return maxsofar;
}

求最接近0的连续子向量和

该问题要求找到和绝对值最小的连续子向量。对于相同向量，若存在和为4与-4的子向量，绝对值均为4，视为最接近0。

操作顺序：暴力遍历比较

入口： 遍历所有子向量组合。
动作： 计算每个子向量的和，并与当前记录的最小绝对值进行比较，更新极值。
注意： 同样可以使用前缀和+排序的方法优化至 O(n log n)，但以下展示基础的 O(n²) 实现以确保逻辑清晰。

#include 

// 辅助函数：返回绝对值更小的数
int closeZero(int x, int y) {
    return (abs(x) < abs(y)) ? x : y;
}

// 求解最接近0的子段和
int findClosestToZero(int v[], int len) {
    int min_abs_val = abs(v[0]); // 初始化为第一个元素的绝对值
    
    for (int i = 0; i < len; i++) {
        int current_sum = 0;
        for (int j = i; j < len; j++) {
            current_sum += v[j];
            if (abs(current_sum) < abs(min_abs_val)) {
                min_abs_val = current_sum;
            }
        }
    }
    return min_abs_val;
}