首页 > 代码库 > IT公司100题-32-求数组的最大子序列的和

IT公司100题-32-求数组的最大子序列的和

2024-07-20 13:28:21   214人阅读

问题描述：
有两个整数序列a, b，大小都为n, 序列元素的值任意整数，无序。
要求：通过交换a, b 中的元素，使得sum(a)-sum(b)，差最小。
例如:
var a=[80, 40, 60, 10, 20, 30];
var b=[10, 20, 50, 40, 30, 20];
 
分析：
近似最优算法：
当前数组a和数组b的和之差为：A = sum(a) – sum(b)，a的第i个元素和b的第j个元素交换后，a和b的和之差为：
A’ = (sum(a) – a[i] + b[j]) – (sum(b) – b[j] + a[i])
= sum(a) – sum(b) – 2 (a[i] – b[j])
= A – 2 (a[i] – b[j])
设x= a[i] – b[j]，A’ = A-2x，只要 0 < x <= A/2，则A’ < A。
所以，目标就是寻找i和j，使得x在0和A/2之间，并且越接近A/2越好。直到找不到这样的x为止。

代码实现：

 

 1 // 32.cc 2 #include <iostream> 3 using namespace std; 4  5 // 计算数组的和 6 int sum(const int* a, int n) { 7     int count = 0; 8     for (int i = 0; i < n; i++) 9         count += a[i];10     return count;11 }12 13 // 交换数组元素得到平衡集14 void balance_swap(int* a, int* b, int n) {15     // a指向和比较大的集合16     if (sum(a, n) < sum(b, n)) {17         int* t = a;18         a = b;19         b = t;20     }21 22     bool loop = true;23     while (loop) {24         loop = false;     25         for (int i = 0; i < n; i++) {26             for (int j = 0; j < n; j++) {27                 int diff = a[i] - b[j];28                 int A = sum(a, n) - sum(b, n);29                 if (diff > 0 && diff < A / 2) {30                     loop = true;31                     int tmp = a[i];32                     a[i] = b[j];33                     b[j] = tmp;34                 }35             }36         }37     }38 }39 40 // 打印数组元素41 void print(const int* a, int n) {42     for (int i = 0; i < n; i++)43         cout << a[i] << " ";44     cout << endl;45 }46 47 int main() {48     int a[] = {80, 40, 60, 10, 20, 30};49     int b[] = {10, 20, 50, 40, 30, 20};50     int n = sizeof(a) / sizeof(int);51 52     balance_swap(a, b, n);53 54     print(a, n);55     print(b, n);56 57     return 0;58 }

 

输出：

$ ./a.exe50 40 60 10 20 3010 20 80 40 30 20

 

 

IT公司100题-32-求数组的最大子序列的和


联系
我们