最大子段和问题的多算法实现

最大子段和问题的多算法实现

1.BF

#include <stdio.h>

void maxSubarrayBruteforce(int arr[], int n) {
    int maxSum = INT_MIN;
    int startIndex = 0;
    int endIndex = 0;

    for (int i = 0; i < n; i++) { //n种可能
        int currentSum = 0;
        for (int j = i; j < n; j++) { //每种可能每次从j=i开始
            currentSum += arr[j];
            if (currentSum > maxSum) { //每次加法后存储最大值
                maxSum = currentSum;
                startIndex = i;	//求到最大后存储当前开始和结束标签
                endIndex = j;
            }
        }
    }

    printf("最大子段和: %d\n", maxSum);
    printf("最大子段: ");
    for (int k = startIndex; k <= endIndex; k++) {
        printf("%d ", arr[k]);
    }
    printf("\n");
}

int main() {
    int arr[] = {-2, 1, -3, 4, -1, 2, 1, -5, 4};
    int n = sizeof(arr) / sizeof(arr[0]);

    maxSubarrayBruteforce(arr, n);

    return 0;
}
/*
  暴力解法的思路是枚举所有可能的子段，计算它们的和，然后找出最大的和。

 */

2.D&C

#include <stdio.h>
#include <limits.h>

// 求三个数中的最大值
int max(int a, int b, int c) {
    if (a >= b && a >= c)
        return a;
    else if (b >= a && b >= c)
        return b;
    else
        return c;
}

// 在跨越中点的情况下找到最大子段和
int maxCrossingSum(int arr[], int low, int mid, int high) {
    int leftSum = INT_MIN;
    int sum = 0;
    for (int i = mid; i >= low; i--) {
        sum += arr[i];
        if (sum > leftSum)
            leftSum = sum;
    }

    int rightSum = INT_MIN;
    sum = 0;
    for (int i = mid + 1; i <= high; i++) {
        sum += arr[i];
        if (sum > rightSum)
            rightSum = sum;
    }

    return leftSum + rightSum;
}

// 递归函数，找到数组的最大子段和
int maxSubarraySum(int arr[], int low, int high) {
    if (low == high)
        return arr[low];

    int mid = (low + high) / 2;

    // 递归求解左右子数组的最大子段和
    int leftMax = maxSubarraySum(arr, low, mid);
    int rightMax = maxSubarraySum(arr, mid + 1, high);
    int crossMax = maxCrossingSum(arr, low, mid, high);

    // 返回左右子数组最大子段和以及跨越中点的最大子段和中的最大值
    return max(leftMax, rightMax, crossMax);
}

int main() {
    int arr[] = {-2, 1, -3, 4, -1, 2, 1, -5, 4};
    int n = sizeof(arr) / sizeof(arr[0]);

    int result = maxSubarraySum(arr, 0, n - 1);

    printf("最大子段和: %d\n", result);

    return 0;
}

/*
  最大子段和问题也可以使用分治法来解决。
  分治法的基本思想是将问题划分为较小的子问题，
  然后递归地解决这些子问题，
  最后将子问题的解合并得到原问题的解。
 */

3.DP

#include <stdio.h>

int max(int a, int b) {
    return (a > b) ? a : b;
}

int maxSubarraySum(int arr[], int n) {
    int maxEndingHere = arr[0];
    int maxSoFar = arr[0];

    for (int i = 1; i < n; i++) {
        // 在当前位置选择要么以前一个位置的子数组结束，要么从当前位置重新开始
        maxEndingHere = max(arr[i], maxEndingHere + arr[i]);
        //最后一个maxEndingHere可能比上一个小了，故不能直接返回maxEndingHere，而要设置一个maxSoFar存当前最大值

        // 更新到目前为止的最大子段和
        maxSoFar = max(maxSoFar, maxEndingHere);
    }

    return maxSoFar;
}

int main() {
    int arr[] = {-2, 1, -3, 4, -1, 2, 1, -5, 4};
    int n = sizeof(arr) / sizeof(arr[0]);

    int result = maxSubarraySum(arr, n);

    printf("最大子段和: %d\n", result);

    return 0;
}

Donate