ACM—最大连续子序列（HDOJ1003）
2024-08-24 11:19:28
HDOJ链接 http://acm.hdu.edu.cn/showproblem.php?pid=1003 不了解题目的朋友可以先看一下题目，在这里就不再详细介绍了。（文章内容和解题思路不完全相同,方法一、二、三、四没有对sequence 全为负数的情况进行考虑，就不再对代码进行更新了，如果需要可看1003解题代码，最下面。）
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.
下面就直接进行分析：
方法一：暴力破解，时间复杂度：O(n^3)
对所有情况的子串进行计算，然后求出和最大的子串。这个就不详细解释了看代码就能明白。
private void test01() {
int maxValue = 0;
for (int i = 0; i < array.length; i++) {// 第一次循环
for (int j = i; j < array.length; j++) {// 第二次循环
int thisMaxValue = 0; // 这里置零
for (int k = j; k < array.length; k++) {// 开始新的循环计算thisMaxValue
thisMaxValue += array[k];
}
if (thisMaxValue > maxValue) {
maxValue = thisMaxValue;
}
}
}
System.out.println(maxValue);
}
方法二：还是暴力破解，时间复杂度：O(n^2) 。需要注意的是和方法一的区别。
public void test02() {
int maxValue = 0;
for (int i = 0; i < array.length; i++) {// 第一次循环
int thisMaxValue = 0;
for (int j = i; j < array.length; j++) {// 第二次循环
thisMaxValue += array[j]; // 这里没有置零，利用了上个thisMaxValue数值
if (thisMaxValue > maxValue) {
maxValue = thisMaxValue;
}
}
}
System.out.println(maxValue);
}
区别：方法一每次都是对子串全部循环一遍，而方法二，利用了第二层循环，不再对子串进行全部循环。
方法三：分治算法，递归求解。时间复杂度：O(nlogn)
public void test03() {
System.out.println(start(array, 0, array.length / 2, array.length - 1));
}
//递归方法
private int start(int[] array, int left, int mid, int right) {
if (left == right) {
return array[left];
}
int leftMaxValue = start(array, left, (left + mid) / 2, mid);// 递归求左子串的最大值
int rightMaxValue = start(array, mid + 1, (mid + right) / 2, right);// 递归求右子串的最大值
/**
开始计算跨两边的最大子序列
toLeftMaxValue <—— MaxSum(mid to left)
toRightMaxValue<—— MaxSum(mid to right)
midMaxValue = toLeftMaxValue +toRightMaxValue;
**/
int toLeftMaxValue = 0;
int tempMaxValue = 0;
for (int i = mid; i >= 0; i--) {
tempMaxValue += array[i];
if (tempMaxValue > toLeftMaxValue) {
toLeftMaxValue = tempMaxValue;
}
}
tempMaxValue = 0;
int toRightMaxValue = 0;
for (int i = mid + 1; i <= right; i++) {
tempMaxValue += array[i];
if (tempMaxValue > toRightMaxValue) {
toRightMaxValue = tempMaxValue;
}
}
//计算出跨左右两边的最大子串和
int midMaxValue = toRightMaxValue + toLeftMaxValue;
//返回本层循环的最大子串和
return Math.max(Math.max(leftMaxValue, midMaxValue), rightMaxValue);
}
需要好好考虑的是为何在计算夸两边最大子串和的时候需要 toRightMaxValue + toLeftMaxValue，考虑明白这个问题，方法三也就明白了。因为 toLeftMaxValue 的子串和 toRightMaxValue 的子串是连接着的，其节点就是mid,所以两者完全可以进行相加以求出跨两边的最大子串和。
方法四：遍历累积。时间复杂度：O(n)。
public void test04() {
int maxValue = 0;
int thisMaxValue = 0;
for (int i = 0; i < array.length; i++) {
thisMaxValue += array[i];
if (thisMaxValue > 0) {
maxValue = thisMaxValue > maxValue ? thisMaxValue : maxValue;
} else { // 当子串不大于零的时候，子串断裂，开始新的子串。
thisMaxValue = 0;
}
}
System.out.println(maxValue);
}
不再解释。
后面还有两种方法没有实现。有兴趣的可以参考这里：http://blog.csdn.net/samjustin1/article/details/52043369
1003的代码更新上：
import java.util.Scanner;
public class Main {
static int maxValue;
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int num = in.nextInt();
int tip = 1;
while (in.hasNextInt()) {
String[] datas = in.nextLine().split(" ");
if (!"".equals(datas[0])) {
getMaxValue(tip++, datas);
if (tip > num) {
break;
}
System.out.println();
}
}
}
private static void getMaxValue(int num, String[] array) {
boolean isAllNegative = true, isFirstPositive = true;//是否都为负数 是否是第一个正数
int maxValue = 0; //最终的最大值
int start = 1, end = 1, thisStart = 1, thisEnd = 1;//最终子串的起始为止 最终的子串结束为止 本次循环的起始位置 本次循环的结束位置
int thisMaxValue = 0; //本次循环的最大值
for (int i = 1; i < array.length; i++) {
if (isAllNegative) {//如果该子串都是负数则不进行累加，负数越加越小
thisMaxValue = Integer.parseInt(array[i]);
} else {//如果包含正数则进行累加
thisMaxValue += Integer.parseInt(array[i]);
}
if (thisMaxValue > 0) {//本次循环的子串大于零则需要和前面的子串进行相加
if (thisMaxValue > maxValue) {//循环子串大于最大值则把本次循环的结果进行保存
isAllNegative = false; //此时，整个串必定包含正数，所以改变标识符
maxValue = thisMaxValue;
thisEnd = i;
if (isFirstPositive) {
thisStart = i;
isFirstPositive = false;
}
start = thisStart;
end = thisEnd;
}
} else if (thisMaxValue < 0) {//本次循环结果小于零时
if (isAllNegative) {//都是负数则对maxValue、start和end进行更新
if (i == 1) {
maxValue = Integer.parseInt(array[i]);
}
if (maxValue < Integer.parseInt(array[i])) {
start = i;
end = i;
maxValue = Integer.parseInt(array[i]);
}
} else {//此时新的子串诞生，记录下本子串的起始位置。
thisMaxValue = 0;
thisStart = i + 1;
}
}
}
System.out.println("Case " + num + ":");
System.out.println(maxValue + " " + start + " " + end);
}
}
最新文章
- PHP interface（接口）的示例代码
- jquery中ajax在firefox浏览器下“object XMLDocument”返回结果的解决办法
- mono for android 各版本下载地址
- 在查询时将查询条件放入Session中，导出时直接根据qpniRGaFiler取查询条件即可
- iOS学习09C语言函数指针
- Openwrt 无法上40MHZ带宽
- Android目标大纲
- EDIUS设置自定义输出的方法
- 机器人学 —— 机器人感知（Kalman Filter）
- 把int类型值转换成int数组（不通过string类型转换）
- jq分页插件
- openURL in APP Extension
- [USACO14DEC]后卫马克Guard Mark
- 【1】mac下面iTerm配置oh-my-zsh教程
- JetBrain系列IDE提示Filesystem Case-Sensitivity Mismatch的解决
- codeforces #305 E Mike and friends
- 用bytomswap进行“跨链”资产转换
- Segment 李超线段树
- Ethereum Dapp Tutorial — Part 1
- Net Core 中间件实现修改Action的接收参数及返回值