C++实现使用动态规划法寻找最大子数组和

思路：
对于这种问题，很自然地我们会想到使用动态规划的方法解决。
假设 dp[i] 是数组 array[0, …, i] 的最大子数组和，则很明显等于数组array[0, …, i + 1]的最大子数组和等于max(dp[i] + array[i], array[i])。

源代码：

//
//  main.cpp
//  MaxSumOfSubArr
//
//  Created by 胡昱 on 2021/11/3.
//

#include 
using namespace std;

int main(int argc, const char * argv[]) {
    // 共m个问题
    int m;
    cin >> m;
    while((m--) > 0) {
        // 初始化数组
        int n;
        cin >> n;
        int* a = new int[n];
        int* dp = new int[n];
        int maxSum;
        
        // 寻找最大子数组和
        cin >> a[0];
        dp[0] = a[0];
        maxSum = dp[0];
        for(int i = 1; i < n; ++i) {
            cin >> a[i];
            dp[i] = max(dp[i - 1] + a[i], a[i]);
            maxSum = max(dp[i], maxSum);
        }
        
        // 输出结果
        cout << maxSum <					
										


					

						
欢迎分享，转载请注明来源：内存溢出
原文地址: http://outofmemory.cn/zaji/5099911.html