算法提高 (一)

一、最大连续子段和

资源限制   时间限制:1.0s   内存限制:256.0MB 问题描述   给出一个长为n的数列,a1,a2,……,an,求和最大的连续子序列,即找到一对(i,j),i<=j,使ai+ai+1+……+aj的和最大,输出这个和 输入格式   第一行为正整数n
  第二行n个用空格分开的整数
  表示a1,a2,……,an 输出格式   一个整数,表示最大连续子序列的和 样例输入   3
  -1 -2 -3 样例输出   -1 数据规模和约定   1<=n<=10^5,-10^5<=ai<=10^5 C++实现(动态规划)
#include<iostream>
#include<cmath>
#include<string>
#include<vector>
#include<math.h>
#include<set>
#include<map>
#include<algorithm>
using namespace std;

int Maximum_subsegment_sum(int n,int *a)
{
    int i, sum=0,temp=0;
    for (i = 0; i < n; i++)
    {
        if (temp > 0)
        {
            temp += a[i];
        }
        else {
            temp = a[i];
        }
        if (temp > sum)
        {
            sum = temp;
        }
        
    }
    return sum;
}
int main()
{
    int i, * a, n;
    cin >> n;
    a = new int[n];
    for (i = 0; i < n; i++)
    {
        cin >> a[i];
    }
    cout << Maximum_subsegment_sum(n, a) << endl;
    return 0;
}

 待补……

上一篇:CSP 2021 惨痛


下一篇:行满秩矩阵为何变成增广矩阵还为满秩