洛谷：P1115：最大子段和


洛谷：P1115：最大子段和

Table of Contents

题目

P1115：最大子段和

分析

分治法解决最大子段和问题的基本思路是：将数组分成两半，最大子段和只可能出现在三个位置之一：

  • 完全在左半部分
  • 完全在右半部分
  • 跨越中点（一部分在左半，一部分在右半）

因此可以得到一个算法步骤：

  1. 分割：找到中点，将数组分成左右两部分
  2. 递归求解：
    1. 递归求左半部分的最大子段和
    2. 递归求右半部分的最大子段和
  3. 合并：计算跨越中点的最大子段和
    1. 从中点向左扫描，找到以中点结尾的最大子段和
    2. 从中点+1向右扫描，找到以中点+1开始的最大子段和
    3. 两者相加得到跨越中点的最大子段和

跨越中点的最大子段和

long long maxCrossingSum(const vector<int>& arr, int left, int mid, int right)
{
    // Find maximum sum for left part ending at mid
    long long leftSum = LLONG_MIN;
    long long sum = 0;
    for (int i = mid; i >= left; i--)
    {
        sum += arr[i];
        leftSum = max(leftSum, sum);
    }

    // Find maximum sum for right part starting from mid+1
    long long rightSum = LLONG_MIN;
    sum = 0;
    for (int i = mid + 1; i <= right; i++)
    {
        sum += arr[i];
        rightSum = max(rightSum, sum);
    }

    return leftSum + rightSum;
}

这个步骤还是很直接的。

注意：找左边和右边各半区间的时候，循环变量的“走向”：左半区间是从mid->1，右半区间是从mid+1->right。这样，能保证这两个区间一定以mid作为分界线，也就可以简单加和得到跨越区间的最大子段和。

独立区间的最大子段和

计算各个独立区间的最大字段和用到了递归和合并（跨越分界点区间的最大子段和）。

long long maxSubarraySum(const vector<int>& arr, int left, int right)
{
    // Base case: single element
    if (left == right)
    {
        return arr
;
    }

    int mid = left + (right - left) / 2;

    // Recursively find maximum sum in left and right halves
    long long leftMax = maxSubarraySum(arr, left, mid);
    long long rightMax = maxSubarraySum(arr, mid + 1, right);

    // Find maximum sum crossing the middle
    long long crossMax = maxCrossingSum(arr, left, mid, right);

    // Return maximum of the three
    return max({leftMax, rightMax, crossMax});
}

代码先是递归计算左右独立区间，然后计算跨越中点的区间，最后返回三者中的最大值。

答案

Solution

思考

（略）

Previous Next