最大圆子阵和的 Java 程序
原文:https://www . geesforgeks . org/Java-program-for-maximum-circular-subarray-sum/
给定 n 个数字(都是+ve 和-ve)，排列成一个圆，求连续数字的最大和。
示例:
Input: a[] = {8, -8, 9, -9, 10, -11, 12}
Output: 22 (12 + 8 - 8 + 9 - 9 + 10)
Input: a[] = {10, -3, -4, 7, 6, 5, -4, -1}
Output: 23 (7 + 6 + 5 - 4 -1 + 10)
Input: a[] = {-1, 40, -14, 7, 6, 5, -4, -1}
Output: 52 (7 + 6 + 5 - 4 - 1 - 1 + 40)
方法 1 最大和可以有两种情况:
- 情况 1: 对最大和有贡献的元素被排列成没有缠绕。示例:{-10，2，-1，5}，{-2，4，-1，4，-1}。在这种情况下，卡丹的算法会产生结果。
- 情况 2: 对最大和有贡献的元素被布置成使得包裹在那里。示例:{10，-12，11}，{12，-5，4，-8，11}。在这种情况下，我们将包装改为非包装。让我们看看如何。贡献元素的包装意味着非贡献元素的不包装，所以找出非贡献元素的总和，并从总和中减去这个总和。为了找出非贡献的总和，反转每个元素的符号，然后运行卡丹的算法。 我们的数组就像一个环，我们必须消除最大连续负数，这意味着在倒排数组中最大连续正数。最后，我们比较两种情况下得到的和，并返回两个和的最大值。
以下是上述方法的实现。
Java 语言(一种计算机语言，尤用于创建网站)
// Java program for maximum contiguous circular sum problem
import java.io.*;
import java.util.*;
class Solution{
public static int kadane(int a[],int n){
int res = 0;
int x = a[0];
for(int i = 0; i < n; i++){
res = Math.max(a[i],res+a[i]);
x= Math.max(x,res);
}
return x;
}
//lets write a function for calculating max sum in circular manner as discuss above
public static int reverseKadane(int a[],int n){
int total = 0;
//taking the total sum of the array elements
for(int i = 0; i< n; i++){
total +=a[i];
}
// inverting the array
for(int i = 0; i<n ; i++){
a[i] = -a[i];
}
// finding min sum subarray
int k = kadane(a,n);
// max circular sum
int ress = total+k;
// to handle the case in which all elements are negative
if(total == -k ){
return total;
}
else{
return ress;
}
}
public static void main(String[] args)
{ int a[] = {1,4,6,4,-3,8,-1};
int n = 7;
if(n==1){
System.out.println("Maximum circular sum is " +a[0]);
}
else{
System.out.println("Maximum circular sum is " +Integer.max(kadane(a,n), reverseKadane(a,n)));
}
}
} /* This code is contributed by Mohit Kumar*/
输出:
Maximum circular sum is 31
复杂度分析:
- 时间复杂度: O(n)，其中 n 为输入数组中的元素个数。 因为只需要数组的线性遍历。
- 辅助空间: O(1)。 因为不需要额外的空间。
注意如果所有数字都是负数，例如{-1，-2，-3}，上述算法就不起作用了。在这种情况下，它返回 0。这种情况可以通过在运行上述算法之前添加一个预检查来查看是否所有数字都是负数来处理。
方法 2 方法:在该方法中，修改 Kadane 的算法，找出最小连续子阵和与最大连续子阵和，然后检查 max_value 与从总和中减去 min_value 后剩下的值之间的最大值。 算法
- 我们将计算给定数组的总和。
- 我们将变量 curr_max，max_so_far，curr_min，min_so_far 声明为数组的第一个值。
- 现在我们将使用卡丹算法来寻找最大子阵和和最小子阵和。
- 检查数组中的所有值:-
- 如果 min_so_far 等于 sum，即所有值都是负的，那么我们返回 max_so_far。
- 否则，我们将计算 max_so_far 和(sum–min _ so _ far)的最大值并返回。
下面给出了上述方法的实现。
输出:
Maximum circular sum is 31
复杂度分析:
- 时间复杂度: O(n)，其中 n 为输入数组中的元素个数。 因为只需要数组的线性遍历。
- 辅助空间: O(1)。 因为不需要额外的空间。
详见最大圆子阵和整篇文章！
版权属于：月萌API www.moonapi.com，转载请注明出处
