Java教程

算法提高 （一）

本文主要是介绍算法提高 （一），对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

一、最大连续子段和

资源限制 　　时间限制：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;
}

 待补……

这篇关于算法提高 （一）的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！
您可能喜欢
栏目导航