最大子段和c++代码

最大子段和问题是指在一个数列中找到一个连续的子数列，使得子数列的和最大。以下是C++代码实现：

#include <iostream>
#include <algorithm>
using namespace std;

int main() {
    int n;
    cin >> n;
    int a[n];
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    int ans = a[0], sum = 0;
    for (int i = 0; i < n; i++) {
        sum += a[i];
        ans = max(ans, sum);
        sum = max(sum, 0);
    }
    cout << ans << endl;
    return 0;
}

相关问题

动态规划最大子段和 c++代码

动态规划最大子段和是一个经典的问题，它可以在一维数组中寻找一个连续子数组，使得该子数组的元素之和最大。以下是 C++ 代码实现：

#include <iostream>
using namespace std;

int maxSubArraySum(int arr[], int n) {
    int max_so_far = arr;
    int curr_max = arr;

    for (int i = 1; i < n; i++) {
        curr_max = max(arr[i], curr_max + arr[i]);
        max_so_far = max(max_so_far, curr_max);
    }
    return max_so_far;
}

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

    int max_sum = maxSubArraySum(arr, n);
    cout << "最大子段和为 " << max_sum << endl;

    return 0;
}

编写程序找出序列的最大子段和 C++代码

以下是一个简单的 C 代码实现，使用 Kadane 算法：

#include <stdio.h>

int maxSubArraySum(int a[], int size) {
    int max_so_far = a[0];
    int curr_max = a[0];
 
    for (int i = 1; i < size; i++) {
        curr_max = (a[i] > curr_max + a[i]) ? a[i] : curr_max + a[i];
        max_so_far = (curr_max > max_so_far) ? curr_max : max_so_far;
    }
    return max_so_far;
}
 
int main() {
    int arr[] = {-2, -3, 4, -1, -2, 1, 5, -3};
    int n = sizeof(arr)/sizeof(arr[0]);
    int max_sum = maxSubArraySum(arr, n);
    printf("Maximum contiguous sum is %d\n", max_sum);
    return 0;
}

该程序使用一个循环遍历数组并更新最大子段和和当前子段和。如果当前元素比当前子段和加上当前元素更大，则更新当前子段和，否则保持不变。在每个迭代中，最大子段和也会相应更新。

此程序的输出为：

Maximum contiguous sum is 7