package com.alipay.math.base;
/**
* 最大子序求和
*
* @author xu.le
*
*/
public class MaxSubsequenceSum {
static int seqStart=0;
static int seqEnd=0;
/**
* 时间复杂度O(n平方)
* @param a
* @return
*/
public static int maxSubsequenceSum(int[] a){
int maxSum=0;//用来存储最大子序和
for(int i=0;i<a.length;i++){
int tempSum=0;//临时最大子序和
for(int j=i;j<a.length;j++){
tempSum+=a[j];
if(tempSum>maxSum){
maxSum=tempSum;
seqStart=i;
seqEnd=j;
}
}
}
return maxSum;
}
/**
* 时间复杂度O(n)
* @param a
* @return
*/
public static int maxSubsequenceSumAdvance(int[] a){
int maxSum=0;
int tempSum=0;
int count=0;
for(int i=0,j=0;i<a.length;j++){
tempSum+=a[j];
if(tempSum>maxSum){
maxSum=tempSum;
if(count==0)
seqStart=i;
seqEnd=j;
count++;
}else {
if(tempSum<0)
tempSum=0;
}
i=j+1;
}
return maxSum;
}
public static void main(String args[]){
int[] i={-2,11,-4,13,-5,2};
int[] j={1,-3,4,-2,-1,6};
int maxSum=maxSubsequenceSumAdvance(i);
System.out.println("maxSum:"+maxSum);
System.out.println("seqStart:"+i[seqStart]);
System.out.println("seqEnd:"+i[seqEnd]);
}
}
分享到:
相关推荐
最大子序和 简单 数组 54 螺旋矩阵 数组 55 跳跃游戏 58 最后一个单词的长度 61 旋转链表 中等 链表 62 不同路径 中等 动态规划 64 最小路径和 中等 动态规划 66 加一 简单 数组 67 二进制求和 70 爬楼梯 简单 动态...
最大子序和 Easy 56 合并区间 Middle 67 二进制求和 Easy 72 编辑距离 Hard 78 子集 Middle 88 合并两个有序数组 Easy 94 不同的二叉搜索树 Middle 95 不同的二叉搜索树 II Middle 110 平衡二叉树 Easy 123
53、最大子序和 56、合并区间 58、最后一个单词的长度 63、加一 67、二进制求和 70、爬楼梯 75、颜色分类 83、删除排序链表中的重复元素 94、二叉树的中序遍历 98、验证二叉搜索树 121、买卖股票的最佳时机I 122、...
最大子序和 Java 54 顺时针打印矩阵 Python 58 最后一个单词的长度 Java 66 加一 Java 67 二进制求和 Java 69 x的平方根 Java 70 爬楼梯 Java 79 单词搜索 Python 83 删除排序链表中的重复元素 Java 88 合并两个...
最大子序和 Java 数组、动态规划 58 最后一个单词的长度 Java 字符串 66 加一 Java 数组、数学 67 二进制求和 Java 数学、字符串 69 x 的平方根 Java 数学、二分查找 70 爬楼梯 Java 动态规划 83 删除排序链表中的...
最大子序和 简单 : 螺旋矩阵 中等 0056 合并区间 中等 0058 最后一个单词的长度 简单 最小路径和 中等 0066 加一 简单 0067 二进制求和 简单 0069 x 的平方根 简单 爬楼梯 简单 编辑距离 困难 最小覆盖子串 困难 ...
译者序. 前言 第一部分 基础知识 引言 第1章 算法在计算中的作用 1.1 算法 1.2 作为一种技术的算法 第2章 算法入门 2.1 插入排序 2.2 算法分析 2.3 算法设计 2.3.1 分治法 2.3.2 分治法分析 ...
最大子序和 56 合并区间 58 最后一个单词的长度 66 加1 67 二进制求和 69 x 的平方根 70 爬楼梯 75 颜色分类 83 删除排序链表中的重复元素 88 合并两个有序数组 99 恢复二叉搜索树 100 相同的树 101 对称二叉树 105 ...
53.最大子序和【贪心算法|字符串|动态规划|回溯算法】: 查看代码 查看原题 66.加一【数组】: 查看代码 查看原题 67.二进制求和【数学|字符串】: 查看代码 查看原题 69.x 的平方根【数学|二分查找】: 查看代码 查看原...
最大子序和 √ --- √ × × 58 最后一个单词的长度 √ --- √ × × 66 加一 √ --- √ × × 67 二进制求和 √ --- √ × × 69 x 的平方根 √ --- √ × × 70 爬楼梯 √ --- √ × × 88 合并两个有序数组 √ --...
最大子序和 58. 最后一个单词的长度 66. 加一 67. 二进制求和 69. x 的平方根 70. 爬楼梯 83. 删除排序链表中的重复元素 88. 合并两个有序数组 100. 相同的树 101. 对称二叉树 104. 二叉树的...
最大子序和 88.95% - 54 螺旋矩阵 98.34% 70.96% 58 最后一个单词的长度 44.30% - 59 螺旋矩阵 II 61.15% 85.79% 62 不同路径 81.48% 26.06% 66 加一 91.08% - 67 二进制求和 99.85% - 69 x 的平
53.第五十三题,最大子序和,动态规划加遍历 58.第五十八题,最后一个单词的长度, 66.第六十六题,加一 67.第六十七题,二进制求和 69.第六十九题,x的平方根,二分法,牛顿迭代法 70.第七十题,爬楼梯,动态规划或...
数组最大连续子序和。动态规划法 leetcode58 字符串最后一个单词的长度 leetcode66 加一 leetcode67 二进制求和,用二进制表示。递归 leetcode69 算术平方根 leetcode70 爬楼梯。斐波拉契数 leetcode83 去除链表重复...
译者序 前言 第一部分 基础知识 第1章 算法在计算中的作用 1.1 算法 1.2 作为一种技术的算法 思考题 本章注记 第2章 算法基础 2.1 插入排序 2.2 分析算法 2.3 设计算法 2.3.1 分治法 ...
王知昆 -《浅谈用极大化思想解决最大子矩形问题》 伍 昱 -《由对称性解2-SAT问题》 项荣璟 -《充分利用问题性质——例析动态规划的"个性化"优化》 许智磊 -《浅谈补集转化思想在统计问题中的应用》 张 宁 -...
译者序. 前言 第一部分 基础知识 引言 第1章 算法在计算中的作用 1.1 算法 1.2 作为一种技术的算法 第2章 算法入门 2.1 插入排序 2.2 算法分析 2.3 算法设计 2.3.1 分治法 2.3.2 分治法分析 ...
答:膾入处理的扫描序:识别并接受从外部输入的处理谤求和其它有关信息。 内部处理的号码分析栏序:根据输入信号和现有状态进行分析、识别,然后决 定下一步任务。 内部处理的路山选择私序:根据号码分析的结果,进行相应...