文章列表
给定一个浮点数组A, 求其中连续子串中最大和。
首先引入一个前缀和数组S, S[i]=Sum{A[0..i]}, 则可以用一个 N^2算法求出最大连续和，即罗列出所有的可能连续字串。
这个问题事实上有线性时间解法，记录max为以A[i]结尾的最大连续和，那么
java 代码
for (i=0; i<n; i++)
max[i]=max{0,max[i-1]+a[i]}
演化问题：
求最接近一个值V的连续和。基本上沿用N^2算法，但对内部循环使用一个优先队列，复杂度降到NlogN.
- 2007-08-10 15:40
- 浏览 1195
- 评论(0)
给定一个数字序列，求其中最长增序列。
假设 A[i] 表示以第i个元素结尾的最长增序的长度，那么F[i+1]需要依次和前面的F[0...i]进行比较，
F[i+1]=max{1, F[i]+1} 且A[i+1]>A[i]
此算法为n^2
优化算法： 根据F的值进行分类，对于一个F值k, 记录下所有F[i]中值为k的最小A[i]在数组D中.
假设已经求得最长增序的长度为m，那么对于新的输入A[t], 在数组D[1..m]中查找最大的比A[t]小的元素D[j], 那么更新D[j+1].
因为数组D是非降的，因而可以使用二分查找，使得算法复杂度降到nlogn的量级。
- 2007-08-10 15:17
- 浏览 774
- 评论(0)
找到了一个解释,期待更深入的。
Class.forName vs ClassLoader.loadClass. There are some subtle differences
between these two APIs. The method call CL.loadClass(C), where CL is our ClassLoader and C is the name of the class to load, queries the ClassLoader directly for the class by name. This in turn relies on ClassLo ...
- 2007-07-19 16:51
- 浏览 820
- 评论(0)