算法_hdoj_1003
2024-09-02 10:11:29
question:
Max Sum
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 324604 Accepted Submission(s): 77195
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
5 6 -1 5 4 -7
7 0 6 -1 1 -6 7 -5
Sample Output
Case 1:
14 1 4
14 1 4
Case 2:
7 1 6
Author
Ignatius.L
idea:
add up the sum each input
memory the max,and update it when the sum more than the max
set the sum as zero when the sum is less than zero,and meanwhile,set the temp as current order of the number and add two
Thinking process:if the sum is still more than zero ,next addition must bigger than it,and it must be less then the last when the sum is negative number,so initialize the sum only when it is negative
source code :
import java.util.Scanner; public class Main {
static Scanner sc = new Scanner(System.in);
public static void main(String[] args) {
// int[] arr = {1,1,3,-2,-4,5,6};
// System.out.println(rec_opt(arr,6));
// System.out.println(rec_opt_circle(arr));
// System.out.println(new int[2][3].length);
// System.out.println(sum_extract(arr,arr.length-1,9));
int group_amount = sc.nextInt();
int counter = 1;
while((group_amount--)>0){
int start = 0;
int max = -9999;
int end = 0;
int sum = 0;
int temp = 1; int len = sc.nextInt(); for (int i = 0;i<len;i++){
sum+= sc.nextInt();
if(sum > max){
max = sum;
start = temp;
end = i+1;
} if(sum<0){
sum = 0;//重新初始化,然后跳转到当前位置重新开始累加
temp = i + 2;
}
}
/**
* Case 1:
* 14 1 4
*/
System.out.println("Case "+(counter++)+":");
System.out.println(max + " " + start + " " + end);
if(group_amount!=0)System.out.println();
}
}
}
hope that I can help you guys XD
that's all
最新文章
- 多功能弹窗控件layer
- MySQL数据库实例参数对比脚本
- GCHandler的使用
- 为什么Java方法里面不能再嵌套方法?
- 通过nsenter连接docker容器
- XSLT
- oc语言学习之基础知识点介绍(三):类方法、封装以及继承的介绍
- 配置Memcache服务器并实现主从复制功能(repcached)(转)
- King&#39;s Quest
- 向RichTextBox控件不停的AppendText数据时,如何把光标的焦点始终显示到最后
- ESMOD北京高级时装艺术学校_百度百科
- Interpolator(插值器)的种类
- CentOS7.0安装Nginx
- 201521123072《java程序设计》第三周学习总结
- 两个port贴合七夕主题,百度输入法的“情感营销”策略
- arcengine导出复本
- 正版STLINK使用注意
- Java项目收藏
- next_permutation(start,end)
- mysql中表里的数据重新设置自增的id的方法