匿名网友
1. 一个有N个元素的整型数组arr，有正有负，数组中连续一个或多个元素组成一个子数组，这个数组当然有很多子数组，求子数组之和的最大值。
public class DiZengZiXuLieMax {
public static void main(String[] args) {
}
public int LIS(int d[],int n){
int b[] = new int[n];
int left,right,mid,len=1;
b[0]=b[1];
for(int i=2;i<=n;++i){
left = 0;
right = 0;
while(left <= right){
mid = (left+right)/2;
if(b[mid] < d[i]) left = mid+1;
else right = mid-1;
}
b[left] = d[i];
if(left > len) len++;
}
return len;
}
}
2. 两个数组中指定位置最大的元素。给定两个已经从小到大排好序的整数数组A和B,请实现函数找到A和B中第K大元素.举例: A=[1,2,3] B=[2,4,6] 当k=1, 返回6, k=2,返回4，应该是两个数组中所有元素合在一起构成的数组中的第K大元素.
public class KMaxNum {
public static void main(String[] args) {
int a[] = {1,2,3};
int b[] = {2,4,6};
int k = 2;
System.out.println( getMax2(a, b, k-1) );
}
public int getMax(int a[], int b[],int k){
if (k <= a.length && k <= b.length)
return a[a.length-1] > b[b.length-1]? a[a.length-1] : b[b.length-1];
else
return -1111;
}
/**
* 思路:将两个数组按从大到小合成一个,合到第k大就停止
* @param a
* @param b
* @param k
* @return
*/
public static int getMax2(int a[], int b[],int k){
int c[] = new int[a.length+b.length];
int m = 0;
int i = a.length-1;
int j = b.length-1;
while( i>=0 && j>=0){
if (a[i] >= b[j]) {
c[m] = a[i];
m++;
i–;
}else {
c[m] = b[j];
m++;
j–;
}
if ( (m-1) == k) {
return c[m-1];
}
}
if(i >=0){
for (int t = i; t >= 0; t–) {
c[m] = a[t];
m++;
if ( (m-1) == k) {
return c[m-1];
}
}
}else if(j >= 0) {
for (int t = j; t >= 0; t–) {
c[m] = b[t];
m++;
if ( (m-1) == k) {
return c[m-1];
}
}
}
return -11111111;
}
}
3. 给定一个排好序的无重复整数数组,请找出其中的最长连续子数组.例如: [1,3,4,5,9,10],则最长连续子数组是[3,4,5,6]
