【算法与数据结构】最大子序列和问题-阿里云开发者社区

开发者社区> 傲海> 正文

【算法与数据结构】最大子序列和问题

简介: (转载请注明出处:http://blog.csdn.net/buptgshengod) 1.题目      给定一个数字序列,其中有正有负,确定最大子序列和。用穷举法最好的结果也是时间复杂度O(n²)。后来看到一个聪明的方法,直接使时间复杂度变为O(n)。 2.解法 (1)穷举法        把所有序列都算出来找到最大的。 /* 最大序列和问题的求解,一组数列有正有负
+关注继续查看

(转载请注明出处:http://blog.csdn.net/buptgshengod

1.题目

     给定一个数字序列,其中有正有负,确定最大子序列和。用穷举法最好的结果也是时间复杂度O(n²)后来看到一个聪明的方法,直接使时间复杂度变为O(n)。

2.解法

(1)穷举法

       把所有序列都算出来找到最大的。
/*
   最大序列和问题的求解,一组数列有正有负,找出其中加起来最大的连续序列。
   以如下序列为例-2,11,-4,13,-5,-2
   算法一:穷举法
 */


public class Test {

	
	public static void main(String[] args)
	{
		int[] list={-2,11,-4,13,-5,-2};
		int i,j;
		int maxsum=0;
		int sum=0;
		
		for(j=0;j<list.length;j++)
		{
			sum=0;
			for(i=j;i<list.length;i++)
		   {
			  	
			  sum+=list[i];
		       if(sum>maxsum)
		     {
		    	 maxsum=sum;
		     }
		   }
		}
		System.out.print(maxsum);
     }
}

(2)联机算法

     联机算法是对读入的数据给出正确答案,每次都判断。
     因为最大子序列不可能以一个负数作为起始。同理也不可能以一个负序列做起始。
public class test {
   
	public static void main(String []args)
   {
		int[] list={-2,11,-4,13,-5,-2};
		int i,j;
		int maxsum=0;
		int sum=0;
		
		for(i=0;i<list.length;i++)
		{
			sum+=list[i];
			if(sum>maxsum)
			{
				maxsum=sum;
			}
			else
			{
				if(sum<0)
					sum=0;
			}
		}
      System.out.print(maxsum);
   }
}  



版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

相关文章
结构化大数据分析平台设计
## 前言  任何线上系统都离不开数据,有些数据是业务系统自身需要的,例如系统的账号,密码,页面展示的内容等。有些数据是业务系统或者用户实时产生的,例如业务系统的日志,用户浏览访问的记录,系统的购买订单,支付信息,会员的个人资料等。
1232 0
海量数据处理的 Top K算法(问题) 小顶堆实现
  问题描述:有N(N>>10000)个整数,求出其中的前K个最大的数。(称作Top k或者Top 10)   问题分析:由于(1)输入的大量数据;(2)只要前K个,对整个输入数据的保存和排序是相当的不可取的。
856 0
项目中树形结构的添加与立即删除该数据问题
  立即添加是可以的,但是想把刚添加的那条数据删除就不行了。得不到数据的id值;   处理方法:我写了一个sql语句,在添加之后,把数据中最大的id值取出来,添加在节点上,这样就可以保证立即添加的数据,就可以立即删除了。
651 0
使用OpenApi弹性释放和设置云服务器ECS释放
云服务器ECS的一个重要特性就是按需创建资源。您可以在业务高峰期按需弹性的自定义规则进行资源创建,在完成业务计算的时候释放资源。本篇将提供几个Tips帮助您更加容易和自动化的完成云服务器的释放和弹性设置。
12037 0
【数据挖掘】数据挖掘算法 组件化思想 示例分析 ( 组件化思想 | Apriori 算法 | K-means 算法 | ID3 算法 )
【数据挖掘】数据挖掘算法 组件化思想 示例分析 ( 组件化思想 | Apriori 算法 | K-means 算法 | ID3 算法 )
8 0
数据结构学习笔记——最大子列和问题
PTA 中国大学MOOC-陈越、何钦铭-数据结构 01-复杂度1 最大子列和问题(20 分) 给定K个整数组成的序列{ N​1​​ , N​2​​ , ..., N​k},“连续子列”被定义为{ N​i , N​i+1​​ , ..., N​j},其中 1≤i≤j≤K。
1025 0
+关注
傲海
著有《机器学习实践应用》,阿里云机器学习PAI产品经理,个人微信公众号&ldquo;凡人机器学习&rdquo;。
302
文章
10
问答
文章排行榜
最热
最新
相关电子书
更多
《2021云上架构与运维峰会演讲合集》
立即下载
《零基础CSS入门教程》
立即下载
《零基础HTML入门教程》
立即下载