C# 实现分治算法：最大子数组与高精度乘法实战

林舟

发布时间：2026-10-16| 4人浏览过

原创

本文将通过 C# 语言深入剖析分治算法的实际应用。内容涵盖两个核心案例：一是如何利用分治策略高效求解金融场景中的“最大子数组问题”以优化投资时机判断；二是如何通过字符串处理结合分治思想实现超越数据类型限制的“大数相乘”。文章提供完整的代码实现，从暴力法到分治法的演进，再到递归底层的细节把控，旨在为开发者提供一套清晰、可执行的算法落地方案。

分治策略的核心逻辑

分治法（Divide and Conquer）是一种将规模为 n 的问题分解为 k 个规模较小的子问题的算法设计策略。这些子问题互相独立且形式与原问题相同。算法通过递归地求解这些子问题，最终将各子问题的解合并得到原问题的解。当问题规模足够小（易于直接解决）时，则停止递归并直接返回结果。

除了本文提到的场景，二分搜索、合并排序、快速排序、汉诺塔等经典问题均可采用此策略。以下将通过具体的 C# 代码演示该策略在两类不同问题中的应用。

应用一：使用分治法求解最大子数组问题

假设我们有一组股票价格波动数据（即相邻两天的价差），目标是找出哪一段连续的日期区间内买入并卖出能获得最大利润。这等价于在数组中寻找和最大的连续子数组。

暴力求解与性能瓶颈

最直观的方法是遍历所有可能的子数组起点 i 和终点 j，计算其累加和并记录最大值。该方法需要三层嵌套循环，时间复杂度高达 O(n^3)，在处理大规模数据时会极度消耗性能。

分治法优化步骤

分治法的核心在于将数组从中间位置 mid 分为两部分：左半区 [low, mid] 和右半区 [mid+1, high]。最大子数组的出现位置只有三种可能：

完全位于左半区： 此时问题递归转化为求解左半区的最大子数组。
完全位于右半区： 同理，转化为求解右半区的最大子数组。
跨越中点： 子数组包含左半区的一部分和右半区的一部分。这种情况下，我们可以通过分别向左和向右寻找最大边界和来求解。

递归结束后，比较这三种情况的结果，取最大值即为全局最优解。这种方法将时间复杂度降低至 O(n log n)。

第1步：构建辅助结构与递归入口

为了封装结果，定义一个 SubArray 结构体包含起始索引、结束索引和总和。主函数负责准备价格波动数组，并调用递归函数。

public class Test : MonoBehaviour
{
    struct SubArray // 封装最大子数组结果
    {
        public int startIndex;
        public int endIndex;
        public int total;
    }

    void Start()
    {
        Suanfa();
    }
    void Suanfa()
    {
        // 原始价格数组
        int[] priceArray = {100, 113, 110, 85, 105, 102, 86, 63, 81, 101, 94, 106, 101, 79, 94, 90, 97};
        // 转换为价格波动数组（当天价格-上一天价格）
        int[] priceFluctuationArray = new int[priceArray.Length - 1];
        for (int i = 1; i < priceArray.Length; i++)
        {
            priceFluctuationArray[i-1] = priceArray[i] - priceArray[i - 1];
        }
        
        // 调用分治求解
        SubArray subArray = GetMaxSubArray(0, priceFluctuationArray.Length - 1, priceFluctuationArray);
        Debug.Log("startIndex：" + subArray.startIndex);
        Debug.Log("endIndex：" + subArray.endIndex);
        Debug.Log("购买日期是第" + subArray.startIndex + "天 出售日期是第" + (subArray.endIndex + 1) + "天");
    }
}

第2步：实现跨越中点的查找逻辑

这是分治法中最关键的非递归部分。我们需要找到包含 mid 的最大子数组。做法是从 mid 向左扫描找到最大前缀和，再从 mid+1 向右扫描找到最大后缀和，两者相加即为跨越中点的最大和。

    static SubArray GetMaxSubArray(int low, int high, int[] array)
    {
        if (low == high) // 递归终止条件：只有一个元素
        {
            SubArray subArray;
            subArray.startIndex = low;
            subArray.endIndex = high;
            subArray.total = array[low];
            return subArray;
        }
        int mid = (low + high) / 2;
        
        // 递归求解左右两部分的跨域问题
        SubArray subArray1 = GetMaxSubArray(low, mid, array);     // 左侧最大子数组
        SubArray subArray2 = GetMaxSubArray(mid + 1, high, array); // 右侧最大子数组

        // --- 求解跨越中点的最大子数组 ---
        // 1. 从mid向左找最大和
        int total1 = array[mid];
        int startIndex = mid;
        int totalTemp = 0;
        for (int i = mid; i >= low; i--)
        {
            totalTemp += array[i];
            if (totalTemp > total1)
            {
                total1 = totalTemp;
                startIndex = i;
            }
        }
        
        // 2. 从mid+1向右找最大和
        int total2 = array[mid+1];
        int endIndex = mid+1;
        totalTemp = 0;
        for (int j = mid+1; j <= high; j++)
        {
            totalTemp += array[j];
            if (totalTemp > total2)
            {
                total2 = totalTemp;
                endIndex = j;
            }
        }
        
        SubArray subArray3;
        subArray3.startIndex = startIndex;
        subArray3.endIndex = endIndex;
        subArray3.total = total1 + total2;
        
        // 比较三种情况，返回最优解
        if (subArray1.total >= subArray2.total && subArray1.total >= subArray3.total)
        {
            return subArray1;
        }
        else if (subArray2.total >= subArray1.total && subArray2.total >= subArray3.total)
        {
            return subArray2;
        }
        else
        {
            return subArray3;
        }
    }

应用二：分治法实现高精度大数相乘

在编程中，标准整型（如 long）有长度限制。当需要处理超过 19 位的大数运算时，必须借助其他手段。这里利用分治思想配合字符串模拟，实现任意长度整数的乘法。

假设我们需要计算 x * y。根据数学公式，可以将 x 拆分为高低位 a, b，将 y 拆分为 c, d。那么：

x * y = a*c*10^n + (a-b)*(d-c)*10^(n/2) + b*d

这种拆分方式可以减少乘法次数。只要拆分的数字小于安全阈值（如9位数），就可以直接进行基础乘法，避免溢出。其余情况则继续递归拆分。

第1步：定义底层算术操作

由于不能使用内置的大数类，必须手动实现字符串形式的加法和减法。加法需处理进位，减法需处理借位及正负号判断。

namespace bigIntMultiply
{
    class Program
    {
        static void Main(string[] args)
        {
           string a = "99999999999999";
           string b = "123456789001234567890";
            Stopwatch sw = new Stopwatch();
            sw.Start();
            string s = Multiply(b, b);
            sw.Stop();
            Console.WriteLine(s);
            Console.WriteLine(sw.Elapsed);
        }
        
        // 字符串模拟乘法操作
        static string Multiply(string x, string y)
        {
            // ... (此处省略符号处理逻辑，主要关注分治核心)
            
            // 递归终止条件：长度较小，直接转换计算
            if (x.Length <= 9 && y.Length <= 9)
            {
                long tmp = long.Parse(x) * long.Parse(y);
                return (tmp == 0) ? "0" : tmp.ToString();
            }
            
            // 拆分 x 为 a, b; y 为 c, d
            // ... (分割逻辑)
            
            string ac = Multiply(a, c);
            string bd = Multiply(b, d);
            // 利用分治公式计算中间项
            string t1 = Multiply(Subtract(a, b), Subtract(d, c));
            string t2 = Add(Add(t1, ac), bd);
            string t3 = Add(Add(Power10(ac, n), Power10(t2, n / 2)), bd).TrimStart('0');
            
            return negative + t3;
        }
        
        // 字符串加法
        static string Add(string x, string y) { /*...*/ }
        // 字符串减法
        static string Subtract(string x, string y) { /*...*/ }
        // 移位操作（模拟乘以10的n次方）
        static string Power10(string num, int n) => num.PadRight(num.Length + n, '0');
    }
}

该实现展示了如何将复杂的数值计算分解为简单的字符级操作。虽然对于极大规模的数据，存在更先进的库或算法（如 FFT 加速），但这种基于字符串的分治乘法清晰地揭示了算法拆解的思维过程。

总结

分治法不仅是理论上的优雅方案，在解决实际工程问题（如金融数据分析、大数运算）时同样具备极高的实用价值。通过 C# 的代码实现我们可以看到：无论是寻找最优路径还是执行极限计算，合理设置递归终止条件、拆分规则以及合并逻辑，是算法成功的关键。以上就是用C#实现分治算法求解股票问题与大数相乘的详细内容，更多关于C#算法与数据结构优化的资料请关注本站其它相关文章！