链接:http://pat.zju.edu.cn/contests/pat-a-practise/1007
题意:经典的最大连续子串问题。
分析:采用最优的O(N) 算法。
#include<stdio.h> int seq[10005]; int main() { // freopen("in.txt", "r", stdin); int n; scanf("%d", &n); int i; for (i = 0; i < n; i++) scanf("%d", &seq[i]); int maxSum = -1; int left, right; int thisSum = 0; int start = 0; int allNeg = 1; for (i = 0; i < n; i++) { if (seq[i] >= 0) allNeg = 0; thisSum += seq[i]; if (thisSum < 0) { thisSum = 0; start = i + 1; } else if (thisSum > maxSum) { maxSum = thisSum; left = seq[start]; right = seq[i]; } } if (allNeg) printf("%d %d %d\n", 0, seq[0], seq[n - 1]); else printf("%d %d %d\n", maxSum, left, right); return 0; }
相关推荐
最大连续子序列和(Maximal Contiguous Subsequence Sum,简称MCSS)问题是一个经典的计算机科学问题,主要涉及算法设计和分析,尤其是动态规划和分治策略。在这个问题中,目标是从一个整数数组中找到一个子序列,...
7. Maximum Subsequence Sum (25) Maximum Subsequence Sum是一个中等难度的算法设计题,要求考生编写一个程序来计算最大子序列和。该题目考察了考生的算法设计能力和数据结构设计能力。 知识点: * 算法设计 * ...
1. Four Elements Sum 2. Rotten Oranges 3. Digit Count [How many X's] 4. Save Ironman 5. Closest Palindrome 6. Check Array Contains Contigous Integer 7. Pairs with Positive and Negative Values 8. ...
2. Maximum Subsequence Sum(25分) 这是一个典型的贪心算法问题,要求学生计算出给定序列的最大子序列和。该问题的时间复杂度为O(n),其中n为序列的长度。学生需要掌握贪心算法的基本概念和技术,以便正确地解决...
2.4 Maximum subarray sum . . . . . . . . . . . . . . . . . . . . . . . . . 21 3 Sorting 25 3.1 Sorting theory . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25 3.2 Sorting in C++ . . ...
c++ C++_leetcode题解674. Longest Continuous Increasing Subsequence.cpp
Maximum Subsequence Sum”可能涉及动态规划,解决寻找数组中最大子序列和的问题,例如Kadane’s Algorithm。 “03-树2. Tree Traversals Again”可能包含树的不同遍历方法,如前序遍历、中序遍历和后序遍历,这些...
在计算机科学中,最大子序列和(Maximum Subsequence Sum,MSS)问题是一个经典的问题,主要涉及在数组或序列中找到具有最大和的连续子序列。这个问题在算法设计和分析中有着广泛的应用,例如在股票交易策略、数据...
最长公共子序列(Longest Common Subsequence,简称LCS)是计算机科学中一种经典的问题,主要涉及字符串或序列的比较和分析。这个问题在文本编辑器的差异计算、生物信息学的DNA序列比对以及程序代码的相似性检测等多...
The Maximum Subsequence is the continuous subsequence which has the largest sum of...Now you are supposed to find the largest sum, together with the first and the last numbers of the maximum subsequence.
Maximum Subsequence Sum 时间复杂度 中等 二分查找 二分查找算法 简单 线性结构 线性表 堆栈 队列 题目名称 考察知识点 难易度 两个有序链表序列的合并 线性表 简单 一元多项式的乘法与加法运算 线性表 中等 ...
动态规划 poj Common Subsequence c++ cpp文件
英文第二版 目录 . . . . . . . ....2.8 War Story: Mystery of the Pyramids ....2.9 Advanced Analysis (*) ....2.10 Exercises ....3.1 Contiguous vs....3.2 Stacks and Queues ....3.3 Dictionaries ....3.4 Binary Search Trees ....
java java_leetcode题解之Increasing Triplet Subsequence.java
java java_leetcodet题解之Longest Harmonious Subsequence.java
java java_leetcode题解之Length of Longest Fibonacci Subsequence.java
北大POJ2533-Longest Ordered Subsequence【O(nlogn)】
在`max-subsequence-sum.js`这个文件中,很可能包含的就是使用JavaScript实现的最大子序列和的示例代码,比如Kadane's Algorithm的实现。通过阅读和理解这个文件,你可以更好地掌握这个问题的解决方案,并将其应用到...
printf("The length of the longest ordered subsequence is: %d\n", longestOrderedSubsequence(nums, numsSize)); return 0; } ``` 在上面的C程序中,我们首先定义了动态规划数组`dp`,然后通过两层循环来填充...