|
#2
rjsp2014-01-10 08:40
|
main函数：
#include "maxsubarray.h"
#include <iostream>
using namespace std;
using namespace maxsubarray;
int main () {
int num[6] = {1, 2 ,4, -1, 1, -1};
Array *a = max_sub_array(num, 0, 5);
cout<<a->left<<" ";
cout<<a->right<<" ";
cout<<a->sum<<endl;
return 0;
}
头文件：
#ifndef MAX_SUB_ARRAY_H
#define MAX_SUB_ARRAY_H
namespace maxsubarray {
struct Array
{
/* data */
int left;
int right;
int sum;
};
Array* max_sub_array(int* array, int left, int right);
Array* max_crossing_sub_array(int* array, int left, int right, int mid);
}
#endif
源文件：
#include "maxsubarray.h"
using namespace maxsubarray;
Array* max_sub_array(int* array, int left, int right) {
if (left == right) {
Array *a = new Array;
a->left = left;
a->right = right;
a->sum = array[left];
return a;
}
int mid = (right - left) / 2 + left;
Array *max_left = max_sub_array(array, left, mid);
Array *max_right = max_sub_array(array, mid+1, right);
Array *max_crossing = max_crossing_sub_array(array, left, right, mid);
if (max_left->sum > max_right->sum)
if (max_left->sum > max_crossing->sum)
return max_left;
else
return max_crossing;
else
if (max_right->sum > max_crossing->sum)
return max_right;
else
return max_crossing;
}
Array* max_crossing_sub_array(const int* array, int left, int right, int mid) {
int max_sum_left = array[mid];
int max_sum_right = array[mid];
int sum = array[mid];
int max_left = mid -1;
int max_right = mid + 1;
int i;
//find the max_left
for (i = mid-1; i >= left; i--) {
sum += array[i];
if (sum > max_sum_left) {
max_sum_left = sum;
max_left = i;
}
}
// find the max_right
sum = array[mid];
for (i = mid+1; i <= right; i++) {
sum += array[i];
if (sum > max_sum_right) {
max_sum_right = sum;
max_right = i;
}
}
Array *a = new Array;
a->left = max_left;
a->right = max_right;
a->sum = max_sum_right + max_sum_left - array[mid];
return a;
}
在linux下用G++ 编译结果：
dp@dp-ThinkPad-Edge-E430:~/Alogrithm/MaxSubArray$ g++ -o main main.cpp maxsubarray.cpp
maxsubarray.cpp: In function ‘maxsubarray::Array* max_sub_array(int*, int, int)’:
maxsubarray.cpp:14:50: error: call of overloaded ‘max_sub_array(int*&, int&, int&)’ is ambiguous
maxsubarray.cpp:14:50: note: candidates are:
maxsubarray.cpp:4:8: note: maxsubarray::Array* max_sub_array(int*, int, int)
In file included from maxsubarray.cpp:1:0:
maxsubarray.h:14:8: note: maxsubarray::Array* maxsubarray::max_sub_array(int*, int, int)
maxsubarray.cpp:15:54: error: call of overloaded ‘max_sub_array(int*&, int, int&)’ is ambiguous
maxsubarray.cpp:15:54: note: candidates are:
maxsubarray.cpp:4:8: note: maxsubarray::Array* max_sub_array(int*, int, int)
In file included from maxsubarray.cpp:1:0:
maxsubarray.h:14:8: note: maxsubarray::Array* maxsubarray::max_sub_array(int*, int, int)
dp@dp-ThinkPad-Edge-E430:~/Alogrithm/MaxSubArray$
希望高手解答