`
breakallerror
  • 浏览: 7213 次
  • 性别: Icon_minigender_1
  • 来自: 合肥
最近访客 更多访客>>
社区版块
存档分类
最新评论

Max Sum 注意这题

阅读更多

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语言)

    ### Max Sum Plus Plus (ACM, C语言) #### 问题描述 本题要求解决一个较为复杂的最大和问题。题目给出了一系列连续整数 \( S_1, S_2, \ldots, S_n \),其中 \( n \leq 1,000,000 \) 且每个元素的值在 \(-32,768\) ...

    2018暨大上机真题1

    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] &gt; current_sum + ...

    一道SQL Server面试题

    请注意,如果存在多个部门在同一天有人员变动,`MAX(CreateTime)`会返回其中任意一个部门的变动时间,而不是所有部门的共同时间。如果需要精确到具体的变动记录,可能需要额外的信息来确定哪个是最后的变动。

    SQL试题16套(全部有准确答案,有上百页)

    聚合函数,如COUNT(), SUM(), AVG(), MAX(), MIN(),用于对一组值进行计算。例如,COUNT(*)可以计算表中的行数,SUM(column)求和,AVG(column)求平均值。 子查询是在查询中嵌套的查询,可以作为其他查询的一部分,...

    自己整理的 神舟面试题 笔试题 有答案 要去神舟数码 软件公司面试的注意咯

    - 其他选项如`SUM`、`AVG`等不适用于日期类型的列。 #### 3. 自动创建唯一索引(Implicit Unique Index Creation) **题目描述**:对于哪两种约束条件,Oracle服务器会自动创建一个唯一的索引? - **正确选项**:B...

    最新整理]微软等公司数据结构+算法面试100题[第1-80题]

    - 遍历数组的同时维护一个全局最大值变量 `maxSum`,每次更新 `dp[i]` 后都检查是否需要更新 `maxSum`。 - **代码实现**(示例): ```c++ int maxSubArray(vector&lt;int&gt;& nums) { int dp = nums[0], maxSum = ...

    C++课后习题答案-6

    需要注意的是,这个排序算法效率较低,实际应用中可能会使用更高效的排序算法如快速排序或归并排序。 6.14 `A`是一个模板类,包含三个模板参数,并提供了求和方法`sum`。这个例子展示了如何创建一个能处理不同类型...

    Java实战经典第四章课后题答案

    在《Java实战经典》这本书的第五章课后题的第一题中,涉及到一个通过循环计算从1!到a!之间所有数的阶乘之和的问题。这里使用了一个简单的循环来实现阶乘的计算,并将结果累加。 **代码分析:** ```java public ...

    Oracle面试题及答案整理.docx

    在这个问题中,我们可以使用 CASE 语句和 SUM 函数来计算每种员工的数量。CASE 语句可以根据不同的条件返回不同的值,而 SUM 函数可以将这些值相加以计算总数。在这个问题中,我们可以使用以下 SQL 语句: ```sql ...

    OCJP 1ZO-851题库

    - **选项F**:将方法声明替换为 `sum(List&lt;Integer&gt; intList)`,这是因为泛型列表 `List&lt;Integer&gt;` 明确指定了元素类型,从而避免了编译器发出的未检查警告。 - **选项C**:将第13行的迭代方式修改为增强型 for 循环...

    火爆出炉:微软等数据结构%2B算法面试100题首次完整亮相[100题V0.1最终完美珍藏版]

    - `maxSum = max(maxSum, dp[i])`。 3. **边界情况** - 如果数组为空,则返回0。 **示例代码** ```c++ int maxSubArraySum(vector&lt;int&gt;& nums) { int maxSum = nums[0]; int dp = nums[0]; for (int i = 1; ...

    acm动态规划50题

    在这两道题中,动态规划的核心思想是状态转移方程,对于每个位置i,我们根据之前的状态(比如dp[i-1])来计算当前位置的最佳状态(dp[i])。这两个题目都强调了在处理大数据量时优化时间复杂度的重要性,以及对空间...

    全国计算机一级EXCEL操作题.pdf

    * 使用sum、average、max、min、correl、forecast、count、if函数等 绝对引用和相对引用 * 绝对引用:公式中引用的单元格地址在公式复制、移动时不变 * 相对引用:公式中引用的单元格地址在公式复制、移动时自动...

    SAS认证考试样题(123题).pdf

    正确答案是 **B**,这显示了PROC PRINT在指定FIRSTOBS和OBS时处理的是401个观测值,而PROC MEANS由于OBS设置为MAX,则处理全部5000个观测值。 - **QUESTION3** 涉及条件语句IF-THEN-ELSE的逻辑判断。题目中使用了...

    Javabase练习题机试题型-1.doc

    Java基础是编程学习的重要部分,本题涉及到的知识点主要涵盖以下几个方面: 1. **素数判断**:素数是大于1且只有1和自身两个正因数的自然数。题目要求判断一个数字是否为素数。在Java中,可以通过循环从2开始到该...

    sql数据库试题及答案!

    1. **数据查询**:这是SQL的基础,涉及SELECT语句的使用,包括选择特定列、过滤行(WHERE子句)、排序(ORDER BY子句)、分组(GROUP BY子句)和聚合函数(如COUNT、SUM、AVG、MAX和MIN)。 2. **数据插入与更新**...

Global site tag (gtag.js) - Google Analytics