divide&conquer:find max array
package max_subarrayy;
import java.lang.Math;
public class max_subarrayy {
private static int[] array;
public static class mark{
private int lom = 100;
private int him;
private int value;
public mark(int a,int b,int c){
lom = a;him = b;value = c;
}
}
public static mark merge(int low,int high){ //return max line
int N = high + low ; // should plus when to get the mid number *high-low,high
double mid = (double)N/2;
if(low == high){return new mark(low,high,array[low]);}
mark leftmax = merge(low,(int)Math.floor(mid));
mark rightmax = merge((int)Math.floor(mid)+1,high);//even number error *Math ceil
mark midmax = findmidmax(low,high,(int)Math.floor((float)N/2));
int k = (Math.max(leftmax.value, rightmax.value) > midmax.value) ? Math.max(leftmax.value, rightmax.value) : midmax.value;
if(k == leftmax.value){return leftmax;}
else if(k == rightmax.value){return rightmax;}
else{return midmax;}
}
public static mark findmidmax(int low,int high,int mid){
int max = array[mid] + array[mid + 1];
int temp = max;
int lom = mid;
int him = mid +1;
for(int i = mid -1;i >= low;i--){
temp = temp + array[i];
if(temp > max){
max = temp;
lom = i;
}
}
temp = max;
for(int i = mid +2;i <= high;i++){// plus 2 *mid +1
temp = temp + array[i];
if(temp > max){
max = temp;
him = i;
}
}
return new mark(lom,him,max);
}
public static void main(String[] args){
int N = args.length;
array = new int[N];
for(int i = 0;i < N;i++){
array[i] = Integer.parseInt(args[i]);
}
mark a = merge(0,N-1);
System.out.println(a.lom + " " + a.him +" " + a.value);
}
}
最新文章
- 从零开始学Python第六周：面向对象基础（需修改）
- StackExchange.Redis 访问封装类
- 解决Tomcat7“At least one JAR was scanned for TLDs yet contained no TLDs”问题
- Android学习笔记——button_activity
- 初学Ajax(一)
- HDU 3974 Assign the task (DFS序 + 线段树)
- 【C语言】01-函数
- bootstrap小结
- 【国家集训队2010】小Z的袜子[莫队算法]
- Django 学习第十一天——中间键和上下文处理器
- HDU 1019(求最小公倍数 **)
- MySQL查看 InnoDB表中每个索引的高度
- nodeclub route
- C#读取“我的文档”等特殊系统路径及环境变量
- 微信授权获取code（微信支付）
- EF框架CodeFirst the model backing the 'PModelEntities' context has changed since the database was created. Consider using Code First Migrations to update the database
- LintCode 402: Continuous Subarray Sum
- [Python爬虫] 之三：Selenium 调用IEDriverServer 抓取数据
- BZOJ2763: [JLOI2011]飞行路线(分层图 最短路)
- 讲一个关于RSA加密算法的故事