Problem Description
Given a sequence a[1],a[2],a[3]......a[n], your job is to calculate the max sum of a sub-sequence. For example, given (6,-1,5,4,-7), the max sum in this sequence is 6 + (-1) + 5 + 4 = 14.
Input
The first line of the input contains an integer T(1<=T<=20) which means the number of test cases. Then T lines follow, each line starts with a number N(1<=N<=100000), then N integers followed(all the integers are between -1000 and 1000).
Output
For each test case, you should output two lines. The first line is "Case #:", # means the number of the test case. The second line contains three integers, the Max Sum in the sequence, the start position of the sub-sequence, the end position of the sub-sequence. If there are more than one result, output the first one. Output a blank line between two cases.
Sample Input
2
5 6 -1 5 4 -7
7 0 6 -1 1 -6 7 -5
Sample Output
Case 1:
14 1 4
Case 2:
7 1 6
Author
Ignatius.L
这个有点要注意的地方
#include <iostream>
using namespace std;
int get(int data[] , int &l , int &r , int dl)
{
int max = -10000000 ;
l = 0 ;
r = 0 ;
int t = 1 ;
int mt = 0 ;
for(int i = 0 ; i < dl ; i++)
{
mt = mt +data[i];
if(mt > max)
{
max = mt;
l = t ; r = i+1 ;
}
if(mt < 0)
{
mt = 0 ;
t = i+2 ;
}
}
return max ;
}
int main()
{
int num ;
cin >> num ;
for(int k = 1 ; k <= num ;k++)
{
int lg = 0 ;
cin >>lg ;
int * data = new int[lg];
for(int i =0 ;i < lg ; i++)
{
cin >>data[i];
}
int l = 0 , r = lg-1 ;
int max = 0 ;
max = get(data , l , r , lg);
cout<<"Case "<<k<<":"<<endl;
cout<<max<<" "<<l<<" "<<r<<endl;
if(k!=num)
cout<<endl;
}
return 0 ;
}
相关推荐
### Max Sum Plus Plus (ACM, C语言) #### 问题描述 本题要求解决一个较为复杂的最大和问题。题目给出了一系列连续整数 \( S_1, S_2, \ldots, S_n \),其中 \( n \leq 1,000,000 \) 且每个元素的值在 \(-32,768\) ...
max_sum = max(max_sum, current_sum) return max_sum def max_subarray_range(arr): max_sum = arr[0] start = end = 0 current_sum = max_sum for i in range(1, len(arr)): if arr[i] > current_sum + ...
请注意,如果存在多个部门在同一天有人员变动,`MAX(CreateTime)`会返回其中任意一个部门的变动时间,而不是所有部门的共同时间。如果需要精确到具体的变动记录,可能需要额外的信息来确定哪个是最后的变动。
聚合函数,如COUNT(), SUM(), AVG(), MAX(), MIN(),用于对一组值进行计算。例如,COUNT(*)可以计算表中的行数,SUM(column)求和,AVG(column)求平均值。 子查询是在查询中嵌套的查询,可以作为其他查询的一部分,...
- 其他选项如`SUM`、`AVG`等不适用于日期类型的列。 #### 3. 自动创建唯一索引(Implicit Unique Index Creation) **题目描述**:对于哪两种约束条件,Oracle服务器会自动创建一个唯一的索引? - **正确选项**:B...
- 遍历数组的同时维护一个全局最大值变量 `maxSum`,每次更新 `dp[i]` 后都检查是否需要更新 `maxSum`。 - **代码实现**(示例): ```c++ int maxSubArray(vector<int>& nums) { int dp = nums[0], maxSum = ...
需要注意的是,这个排序算法效率较低,实际应用中可能会使用更高效的排序算法如快速排序或归并排序。 6.14 `A`是一个模板类,包含三个模板参数,并提供了求和方法`sum`。这个例子展示了如何创建一个能处理不同类型...
在《Java实战经典》这本书的第五章课后题的第一题中,涉及到一个通过循环计算从1!到a!之间所有数的阶乘之和的问题。这里使用了一个简单的循环来实现阶乘的计算,并将结果累加。 **代码分析:** ```java public ...
在这个问题中,我们可以使用 CASE 语句和 SUM 函数来计算每种员工的数量。CASE 语句可以根据不同的条件返回不同的值,而 SUM 函数可以将这些值相加以计算总数。在这个问题中,我们可以使用以下 SQL 语句: ```sql ...
- **选项F**:将方法声明替换为 `sum(List<Integer> intList)`,这是因为泛型列表 `List<Integer>` 明确指定了元素类型,从而避免了编译器发出的未检查警告。 - **选项C**:将第13行的迭代方式修改为增强型 for 循环...
- `maxSum = max(maxSum, dp[i])`。 3. **边界情况** - 如果数组为空,则返回0。 **示例代码** ```c++ int maxSubArraySum(vector<int>& nums) { int maxSum = nums[0]; int dp = nums[0]; for (int i = 1; ...
在这两道题中,动态规划的核心思想是状态转移方程,对于每个位置i,我们根据之前的状态(比如dp[i-1])来计算当前位置的最佳状态(dp[i])。这两个题目都强调了在处理大数据量时优化时间复杂度的重要性,以及对空间...
* 使用sum、average、max、min、correl、forecast、count、if函数等 绝对引用和相对引用 * 绝对引用:公式中引用的单元格地址在公式复制、移动时不变 * 相对引用:公式中引用的单元格地址在公式复制、移动时自动...
正确答案是 **B**,这显示了PROC PRINT在指定FIRSTOBS和OBS时处理的是401个观测值,而PROC MEANS由于OBS设置为MAX,则处理全部5000个观测值。 - **QUESTION3** 涉及条件语句IF-THEN-ELSE的逻辑判断。题目中使用了...
Java基础是编程学习的重要部分,本题涉及到的知识点主要涵盖以下几个方面: 1. **素数判断**:素数是大于1且只有1和自身两个正因数的自然数。题目要求判断一个数字是否为素数。在Java中,可以通过循环从2开始到该...
1. **数据查询**:这是SQL的基础,涉及SELECT语句的使用,包括选择特定列、过滤行(WHERE子句)、排序(ORDER BY子句)、分组(GROUP BY子句)和聚合函数(如COUNT、SUM、AVG、MAX和MIN)。 2. **数据插入与更新**...