给定一个整数数组,数组里可能有正数、负数和零。数组中连续的一个或多个整数组成一个子数组,每个子数组都有一个和。假设允许交换数组中任意两个数的位置,只允许交换一次,求交换后的最大子数组和,用C语言实现可执行代码
时间: 2024-03-09 15:46:25 浏览: 25
leetcode卡-FirstMissingPositives:第一个缺失的正数
以下是一个C语言实现的交换一次后的最大子数组和代码:
```c
#include <stdio.h>
int max(int a, int b) {
return a > b ? a : b;
}
int maxSubArraySum(int arr[], int n) {
int max_so_far = arr[0];
int curr_max = arr[0];
int max_element = arr[0];
int min_element = arr[0];
for (int i = 1; i < n; i++) {
curr_max = max(arr[i], curr_max + arr[i]);
max_so_far = max(max_so_far, curr_max);
max_element = max(max_element, arr[i]);
min_element = max(min_element, arr[i]);
}
if (max_so_far <= 0)
return max_element;
int ans = max_so_far;
for (int i = 0; i < n; i++) {
if (arr[i] == max_element)
arr[i] = min_element;
else if (arr[i] == min_element)
arr[i] = max_element;
curr_max = arr[0];
max_so_far = arr[0];
for (int j = 1; j < n; j++) {
curr_max = max(arr[j], curr_max + arr[j]);
max_so_far = max(max_so_far, curr_max);
}
ans = max(ans, max_so_far);
if (arr[i] == max_element)
arr[i] = min_element;
else if (arr[i] == min_element)
arr[i] = max_element;
}
return ans;
}
int main() {
int arr[] = {1, 2, 3, -4, 5, -6, 7, -8, 9};
int n = sizeof(arr) / sizeof(arr[0]);
int max_sum = maxSubArraySum(arr, n);
printf("交换一次后的最大子数组和为:%d\n", max_sum);
return 0;
}
```
该代码的思路是先计算出原始数组的最大子数组和,然后枚举交换数组中的每一对元素,并重新计算最大子数组和。最终返回交换一次后得到的最大子数组和。
阅读全文