HDU1003 java
·
题目描述
Max Sum
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 406886 Accepted Submission(s): 99047
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
思路
这道题首先想到的暴力枚举，就是在每个位置遍历其的最大子序和，然后最大输出结果，但是暴力枚举的时间复杂度为O（N^2），所以我想到一个更优化的方法——动态规划。经过观察规律，我们换一个思路，就是其以求i结尾的最大子序和，但是怎么求i结尾的最大子序和呢，我们已经知道当是第一个元素的时候最大子序和就是这个数本身，比如我们求以i=3结尾的最大子序和，怎么求呢，我们发现i=3的最大子序和的结果无非两种
情况1：就只有本身一个数
情况2：本身的这个数加上i=2的最大子序列和
我们要求最大子序和，那么就得到了以第i个结尾的最大子序和为max(a[i],a[i]+dp[i-1])
a[i]+dp[i-1]的意思是延续前面的最大子序
a[i]的意思是另起炉灶，本质就是前面的子序和为负数。
这道题解决方法——动态规划
状态定义
dp[i] = 以索引 i 结尾的最大子序和。状态转移方程：
dp[i] = max( a[i], dp[i-1] + a[i] )
最终结果：
最大子序和不一定是以最后一个元素结尾的，所以最终的答案是
dp 数组中的最大值。优化过程：
因为dp[i]只用到了dp[i-1]，因此我们不需要整个数组，用一个变量currentSum记录当前的最大子序和（初始为第一个数），用一个变量start记录这个子序列的开始坐标，用一个变量end记录这个子序列的结束坐标，接着用一个max_start记录最大的子序和的开始坐标，用一个max_end记录最大的子序和的结束坐标，用一个max_sum记录最大子序和。
如果当前的值大于前序和加上当前值的化，更新当前的移动指针开始坐标和结束坐标都为当前的坐标，并且更新当前以i结尾的最大子序和，反之，就是延续前面的子序和，只要更新当前的结束坐标就可以了，currentSum的值更新为前序和加当前下标的值，最后判断是否需要更新最大子序和的坐标和最大子序和。
Java实现1：
Java实现2：
因为Java代码1的时间复杂度为O（N）已经到达最优，空间复杂度为O（N），空间复杂度没有达到最优，因此我们在Java代码1的基础上对其进行优化得到了Java代码2的代码，优化实现了空间复杂度为O（1）。主要优化过程是将原来用数组存储的输入数据用一个变量存储。
Agent 垂直技术社区，欢迎活跃、内容共建。
更多推荐
14
0- 0
已为社区贡献2条内容
所有评论(0)