1007:连续和最大子串。
O(n)时间即可完成,不需存储空间。
#include<iostream>
using namespace std;
int main()
{
int n;
int max;
int sum;
bool isfirst=true;
int num;
int low;
int high;
int tmp;
int first;
int last;
cin>>n;
for(int i=0;i<n;i++)
{
cin>>num;
if(isfirst)
{
isfirst = false;
sum=num;
max = num;
low = num;
tmp = num;
high = num;
}
else
{
sum += num;
}
if(tmp==-1)
tmp = num;
if(sum>max)
{
max = sum;
low = tmp;
high = num;
}
if(sum<0)
{
sum=0;
tmp = -1;
}
if(i==0)
first = num;
if(i ==n-1)
last = num;
}
if(max < 0)
cout<<0<<" "<<first<<" "<<last;
else
cout<<max<<" "<<low<<" "<<high;
}
分享到:
相关推荐
Finding Maximum Contiguous Subsequence Sum using divide-and-conquer approach
北大POJ2533-Longest Ordered Subsequence【O(nlogn)】
北大POJ2533-Longest Ordered Subsequence 解题报告+AC代码
最大子序列和算法的运行时间 衡量执行时间
北大POJ2533-Longest Ordered Subsequence【O(n^2)】
最长公共子序列问题,动态规划法
前言k-Maximum Subsequence Sum - 模型结合这个模型的性质,我们可以发现我们每次要么选择一个与已有区间完全不相交的区间,要么从已有区间中
最大子序列和该算法采用向量(数组)并找到它的最大子序列和: node max-subsequence-sum.js [2,-4,6,8,-10,100,-6,5]
最长回文子序列 动态规划 | 第 12 组(最长回文子序列)( )
算法设计类源码。使用动态规划的方式计算两个字符串的最大公共子序列。
最长公共子序列 这是一个实施动态编程以查找最长公共子序列的项目,该项目已作为ITCS-6114 / 8114:算法和数据结构课程的一部分进行。 程序和数据结构设计:给定的项目被编写为3个单独的程序。...
longest-common-subsequence longest-consecutive-sequence max-area-of-island next-greater-element-ii serialize-and-deserialize-binary-tree subarray-sum-equals-k binary-tree-preorder-traversal n-queens-...
The Maximum Subsequence is the continuous subsequence which has the largest sum of its elements. For example, given sequence { -2, 11, -4, 13, -5, -2 }, its maximum subsequence is { 11, -4, 13 } with ...
动态规划 poj Common Subsequence c++ cpp文件
最长上升子序列(n·log(n)) Longest-Increasing-Subsequence(n·log(n)) 倍增法求最近公共祖先 Lowest-Common-Ancestor(Doubling) 朴素的矩阵乘法 Matrix-Multiplication(Naive) 归并排序 Merge-Sort 最小堆 ...
LCS Longest (maximum) common subsequence
The Complexity of Word Circuits.- On the Density of Regular and Context-Free Languages.- Extensions of the Minimum Cost Homomorphism Problem.- The Longest Almost-Increasing Subsequence.- Universal ...
Column 8: Compute the maximum-sum subsequence in an array maxsum.c -- Time four algs: n3, n2, n log n, n. Column 9: Code tuning programs genbins.c -- Profile this, then try a special-purpose ...
Longest Ordered Subsequence,算法分析与设计,C语言程序