- 浏览: 467538 次
- 性别:
- 来自: 北京
文章分类
最新评论
-
pyl574069214:
1楼的方法可用
iText操作错误:PdfReader not opened with owner password -
pyl574069214:
谢谢
iText操作错误:PdfReader not opened with owner password -
ggyyso:
解决方法:import java.lang.reflect.F ...
iText操作错误:PdfReader not opened with owner password -
思念-悲伤:
谢了!!!
Exception loading sessions from persistent storage -
u012380013:
加上bos.flush(); 是成功的
Java解压缩zip文件
给定一个数组,求出数组中连续的一些元素使其和的值最大。如果所有元素都为正数,显然整个数组即为所求的。如果所有元素的值为负数,则所求的最大值为0.
这是在编程珠玑上看到的,其时间复杂度由O(n3)减为O(n)了。
public class MaxSum { public static void main(String[] args) { int[] arr = new int[]{31, -41, 59, 26, -53, -58, -97, -93, -23, -84}; MaxSum ms = new MaxSum(); ms.Max(arr); ms.Max2(arr); ms.Max3(arr); int max = ms.Max4(arr, 0, arr.length-1); System.out.println("Max sum is " + max); ms.Max5(arr); } //方法1: 时间复杂度为O(n*n*n) public void Max(int[] arr) { int max = 0; int sum = 0; int left = -1; int right = -1; for(int i=0; i<arr.length; i++) { for(int j=i; j<arr.length; j++) { sum = 0; for(int k=i; k<=j; k++) { sum = sum + arr[k]; } if(sum > max) { left = i; right = j; max = sum; } } } if(right > 0) { System.out.println("Max is from element " + left + "(" + arr[left] + ") to element " + right + "(" + arr[right] + "), max sum is " + max); } else if(right == 0) { System.out.println("Max sum is " + arr[0]); } else { System.out.println("Max sum is 0 ."); } } //方法2:时间复杂度为O(n*n) public void Max2(int[] arr) { int max = 0; int sum = 0; int left = -1; int right = -1; for(int i=0; i<arr.length; i++) { sum = 0; for(int j=i; j<arr.length; j++) { sum = sum + arr[j]; if(sum > max) { left = i; right = j; max = sum; } } } if(right > 0) { System.out.println("Max is from element " + left + "(" + arr[left] + ") to element " + right + "(" + arr[right] + "), max sum is " + max); } else if(right == 0) { System.out.println("Max sum is " + arr[0]); } else { System.out.println("Max sum is 0 ."); } } //方法3:时间复杂度为O(n*n) public void Max3(int[] arr) { int max = 0; int sum = 0; int left = -1; int right = -1; int[] temp = new int[arr.length+1]; temp[0] = 0; for(int i=0; i<arr.length; i++) { temp[i+1] = temp[i] + arr[i]; } for(int i=0; i<arr.length; i++) { for(int j=i; j<temp.length; j++) { sum = temp[j] - temp[i]; if(sum > max) { left = i; right = j-1; max = sum; } } } if(right > 0) { System.out.println("Max is from element " + left + "(" + arr[left] + ") to element " + right + "(" + arr[right] + "), max sum is " + max); } else if(right == 0) { System.out.println("Max sum is " + arr[0]); } else { System.out.println("Max sum is 0 ."); } } //方法4:时间复杂度为O(n*logn) public int Max4(int[] arr, int left, int right) { int sum = 0; int max = 0; int max1 = 0; int max2 = 0; int middle = 0; if(left > right) { return 0; } else if(left == right) { return (arr[left] > 0 ? arr[left] : 0); } middle = (left + right)/2; for(int i=middle; i>=left; i--) { sum = sum + arr[i]; if(sum > max1) { max1 = sum; } } sum=0; for(int i=middle+1; i<=right; i++) { sum = sum + arr[i]; if(sum > max2) { max2 = sum; } } max = max1+max2; int temp1 = Max4(arr, left, middle); int temp2 = Max4(arr, middle+1, right); if(temp1 > max) { max = temp1; } if(temp2 > max) { max = temp2; } return max; } //方法5:时间复杂度为O(n) public void Max5(int[] arr) { int max1 = 0; int max2 = 0; int left = -1; int right = -1; int temp = 0; int count = 0; for(int i=0; i<arr.length; i++) { temp = (max1+arr[i]); if(temp > 0) { count++; if(count == 1) left = i; max1 = temp; if(max1 > max2) { right = i; max2 = max1; } } else { max1 = 0; count = 0; } } if(right > 0) { System.out.println("Max is from element " + left + "(" + arr[left] + ") to element " + right + "(" + arr[right] + "), max sum is " + max2); } else if(right == 0) { System.out.println("Max sum is " + arr[0]); } else { System.out.println("Max sum is 0 ."); } } }
输出为:
Max is from element 2(59) to element 3(26), max sum is 85 Max is from element 2(59) to element 3(26), max sum is 85 Max is from element 2(59) to element 3(26), max sum is 85 Max sum is 85 Max is from element 2(59) to element 3(26), max sum is 85
发表评论
-
java中final关键字的使用
2013-05-31 10:04 5039java中final关键字的使用 1. 用final修饰基 ... -
Java类的初始化
2010-02-01 18:28 1195如下面代码 public class Test1 ... -
Java之Exception与try语句
2010-02-01 18:21 1334代码如下: public class Test1 ... -
java之对象引用static变量
2010-01-18 09:53 1574如下面代码 public class Test { ... -
java之catch语句
2010-01-13 20:16 1973如下面代码: public class Test { ... -
java之static变量
2010-01-13 20:07 1126如下面代码: public class Test { ... -
java之继承
2010-01-13 20:03 1064如下面代码: public class Test { ... -
java内部类
2010-01-13 10:46 1090如下面代码: public class OuterIn ... -
java基础之"=="操作符
2010-01-12 19:44 1069如下: public class Test { ... -
java之动态绑定和静态绑定
2010-01-11 11:22 1328如下面代码: package cn.lifx.test; ... -
java之String变量和“==”操作符(2)
2010-01-11 10:51 1317如下面代码: public class StringTest ... -
java之String变量和“==”操作符(1)
2010-01-06 16:35 1187先看下面的代码,有助于后面的理解。 public cl ... -
汉字截取问题
2010-01-04 15:01 1221如下 public class Test { p ... -
求几个整数的最小公倍数和最大公约数
2009-12-31 16:23 1385下面的方法是用递归解决的。如求几个整数的最小公倍数 ... -
java之final, finally, finalize的区别
2009-12-25 15:43 14921. final 用于声明属性,方法和类,分别表示属性不 ... -
java之抽象类和接口
2009-12-25 11:15 1174如下代码,是使用接口时需要注意的问题。 public int ... -
java之try与finally语句(2)
2009-12-25 11:07 1383接上一篇,跟上一篇代码差不多,就是修改了a的值为double类 ... -
java之try与finally语句
2009-12-24 21:42 1508如下面的代码,结果就不解释了。 public clas ... -
java的静态方法和非静态方法
2009-12-24 11:11 1264如下面的代码 public class Test { ... -
接着看java线程问题
2009-12-18 19:26 1012接上一篇,继续看看java线程问题。当然,下面的程序或者说用法 ...
相关推荐
在一个数组中找出连续元素的最大值,时间复杂度o(n),空间复杂度o(n)
数组中连续的一个或多个整数组成一个子数组,每个子数组都有一个和。 求所有子数组的和的最大值。要求时间复杂度为O(n)。 例如输入的数组为1, -2, 3, 10, -4, 7, 2, -5,和最大的子数组为3, 10, -4, 7, 2, 因此...
有1个包含N个整数的数组A,定义1个数组的美丽值为数组中所有不同整数的和。求数组A的所有连续子序列的美丽值之和。
求元素组合成连续子数组之和最大的子数组,要求时间复杂度为O(n)
编写一个在具有m行n列的二维数组各元素中找出最大元和最小元并显示在屏幕上的函数模板,并通过主函数对它进行调用以验证其正确性。例如,可设计该函数模板的原型为: template <class Type> void maxMin (Type *A,...
一个有 n 个元素的数组,这 n 个元素既可以是正数也可以是负数,数组中连续的一个或多个元素可以组成一个连续的子数组,一个数组可能有多个这种连续的子数组,求子数组的最大值。例如,对于数组 [1,-2,4,8,-4,7...
最大子数组和是一道经典的算法问题,其目的是在一个数组中找到一个连续的子数组,使得该子数组的和最大。最大子数组和问题可以通过动态规划算法来解决,时间复杂度为O(n),其中n为数组长度。 最大子数组和的具体...
假设X:[1:n] 是实数数组, L 是一个固定的正整数L ≤ n。X的L 子数组是数组X 的L 连续元素的任意序列。...X[1:n] 和一个正整数L ≤n ,并返回具有最大波谷的子数组L 的起始位置,并根据n 和L 分析算法的时间复杂度。
给定一个n个元素的数组,数组元素全部为整数,负数,正数和0均有可能存在,设设计一个算法,找出连续的几个数组元素相乘积最大
包含促销购物和树变森林的动态规划一个序列由N个元素组成,现希望从该序列中挑选出至少F个连续的元素,使这些数的均值(挑选出的连续数之和/数的个数)最大。 输入要求:输入第1行包含两个整数N和F,其后的1行包含N...
存储扩展算法n2编程c 写一个时间复杂度尽可能低的程序,求一个一维数组(N个元素)中的最长递增子序列的长度。例如:在序列1,-1,2,-3,4,-5,6,-7中,其最长的递增子序列为1,2,4,6 或者 -1,2,4,6。(编程之...
(1)可以只给部分元素赋初值,当{}中值的个数少于元素个数时,只给前面部分元素赋初值,未赋值的元素会赋予与数组元素类型相关的特定值,整型为0,浮点型为0.0,字符型为'\0'。 补充说明:字符'0'和'\0'区别: ...
给定由n整数(可能为负数)组成的序列 {a1,a2,…,an},求该序列形如ai+ai+1,…,+aj的子段和的最大值。当所有的整数均为负数时定义其最大子段和为0。 Input 输入包含多组测试数据。第一行为一个整数C,表示有C组...
要求:找到一个具有最大和的连续子数组(子数组最少包含一个元素),返回其最大和,要求时间复杂度为 O(n)。即将之前累加和加上当前值与当前值做比较, 如果将之前累
数组元素也称为下标变量,在内存中是连续存放的,有前后关系。 a 0 1 2 3 4 5 6 7 8 9 a[0] ≠ a0 a[i] ≠ ai 数组的基本概念 一个下标的数组称为一维数组,如 a[0],a[1],… 两个下标的数组称为二维数组,如a[0][0],...
当{ }中值的个数少于元素个数时,只给前面部分元素赋值。例如: static int a[10]={0,1,2,3,4};表示只给a[0]~a[4]5个元素赋值,而后5个元素自动赋0值。 2.只能给元素逐个赋值,不能给数组整体赋值。 例如给十个元素...
下面的流程图在该数组中寻找连续排列的若干个元素,使其和达到最大值,并输出其起始下标K、元素个数L以及最大的和值M。 例如,若数组元素依次为3,-6,2,4,-2,3,-1,则输出K=3,L=4,M=7。该流程图中考察了A[1:N...
(10)编写一个程序实现如下功能:调用名为tj的函数,求一个二维数组中正数、负数的代数和,以及零的个数。 (11)编写一个程序实现如下功能:调用一个名为gm的函数,该函数实现简单的加密。加密方法如下:先定义...