请分别用暴力穷举法(3层循环),优化穷举法(2层循环),问题转化—等效子问题求解的动态规划法(1层循环),分治法(递归求解)这4种不同的思路(即算法思想)实现问题求解。 题目描述: 给定一个整数数组{A1,A2,…,An},连续子序列和的定义为: SubSum(i,j)=Ai+Ai+1+…+Aj-1+Aj 试求解输入数组的连续子序列和的最大值。如果所有的整数都是负数,那么最大连续子数列为0。 如有一个数组{1, -5, 8, 3, -4, 15, -8},则查找其中连续和最大的相邻串的值,最大值为:8+3+-4+15=22。
时间: 2023-05-21 22:03:27 浏览: 147
好的,我将扮演 CSDN 开发的 C知道,我会尽力回答你的问题。对于你的第一个问题,以下是我的回答:
暴力穷举法(3层循环):
我们可以使用三层循环来枚举所有可能的连续子序列,然后计算它们的和,最后找到最大的和。具体实现如下:
int maxSubArraySum(int arr[], int n)
{
int max_sum = INT_MIN;
for (int i = 0; i < n; i++)
{
for (int j = i; j < n; j++)
{
int sum = 0;
for (int k = i; k <= j; k++)
{
sum += arr[k];
}
if (sum > max_sum)
{
max_sum = sum;
}
}
}
return max_sum;
}
优化穷举法(2层循环):
我们可以使用两层循环来枚举所有可能的连续子序列,然后计算它们的和,最后找到最大的和。具体实现如下:
int maxSubArraySum(int arr[], int n)
{
int max_sum = INT_MIN;
for (int i = 0; i < n; i++)
{
int sum = 0;
for (int j = i; j < n; j++)
{
sum += arr[j];
if (sum > max_sum)
{
max_sum = sum;
}
}
}
return max_sum;
}
问题转化—等效子问题求解的动态规划法(1层循环):
我们可以使用动态规划来解决这个问题,具体来说,我们定义一个数组 dp,其中 dp[i] 表示以第 i 个元素结尾的最大子序列和。然后,我们可以使用以下递推公式来计算 dp[i]:
dp[i] = max(dp[i-1] + arr[i], arr[i])
最后,我们可以遍历 dp 数组,找到其中的最大值即可。具体实现如下:
int maxSubArraySum(int arr[], int n)
{
int max_sum = INT_MIN;
int dp = arr[0];
for (int i = 1; i < n; i++)
{
dp = max(dp + arr[i], arr[i]);
max_sum = max(max_sum, dp);
}
return max_sum;
}
分治法(递归求解):
我们可以使用分治法来解决这个问题,具体来说,我们将数组分成两个部分,分别求出左半部分的最大子序列和、右半部分的最大子序列和以及跨越中点的最大子序列和,然后取这三个值的最大值即可。具体实现如下:
int maxSubArraySum(int arr[], int l, int r)
{
if (l == r)
{
return arr[l];
}
int m = (l + r) / 2;
int left_max = maxSubArraySum(arr, l, m);
int right_max = maxSubArraySum(arr, m+1, r);
int cross_max = arr[m];
int sum = arr[m];
for (int i = m-1; i >= l; i--)
{
sum += arr[i];
cross_max = max(cross_max, sum);
}
sum = arr[m+1];
for (int i = m+2; i <= r; i++)
{
sum += arr[i];
cross_max = max(cross_max, sum);
}
return max(left_max, max(right_max, cross_max));
}
int maxSubArraySum(int arr[], int n)
{
return maxSubArraySum(arr, 0, n-1);
}
希望这些回答能够帮助你!