/********************************* * 日期:2015-01-29 * 作者:SJF0115 * 题目: 在由N个正整数的集合S中,找出最大元素C,满足C=A+B,其中A,B都是集合S中的元素 * 来源:百度 * 博客: **********************************/ #include <iostream> #include <algorithm> using namespace std; int FindSum(int A[],int n){ // 排序 sort(A,A+n); int left,right,sum; // i = C for(int i = n - 1;i >= 2;--i){ left = 0,right = i - 1; // 判断是否有A + B = i while(left < right){ sum = A[left] + A[right]; if(sum == A[i]){ return A[i]; }//if else if(sum > A[i]){ --right; } else{ ++left; } }//while }//for return -1; } int main(){ int A[] = {5,7,3,0,9,11,8,13,100}; int n = 9; cout<<FindSum(A,n)<<endl;; return 0; }时间复杂度O(n*n)
public class Findsunc {
public static void main(String[] args) {
// TODO Auto-generated method stub
int s[] = {1,2,3,4,5,7,6,98};
int ans = FindC(s);
System. out .println(ans);
}
//查找满足C=A+B的最大值
public static int FindC( int arr []){
quick_sort(arr,0,arr.length-1);
for ( int max = arr.length-1;max>1;max--){
int C= arr[max];
int i=0,j=max-1;
while (j>i){
if (arr[i]+arr[j]==C)
return C;
if (arr[i]+arr[j]<C){
i++;
}
else {
j--;
System. out .println(arr[j]);
}
}
}
return -1;
}
static void quick_sort( int arr[], int left, int right) {
int dp;
if (left < right) {
dp = partition(arr, left, right);
quick_sort(arr, left, dp - 1);
quick_sort(arr, dp + 1, right);
}
}
static int partition( int arr[], int left, int right) {
int pivot = arr[left];
while (left < right) {
while (left < right && arr[right] >= pivot)
right--;
if (left < right)
arr[left++] = arr[right];
while (left < right && arr[left] <= pivot)
left++;
if (left < right)
arr[right--] = arr[left];
}
arr[left] = pivot;
return left;
}