Trouver une somme maximale de sous-traits circulaires
#include <iostream>
using namespace std;
int kadane(int arr[], int n)
{
int currentSum = 0;
int maxSum = INT_MIN;
for (int i = 0; i < n; i++)
{
currentSum += arr[i];
if (currentSum < 0)
{
currentSum = 0;
}
maxSum = max(maxSum, currentSum);
}
return maxSum;
}
int main()
{
//Input Array
int n;
cin >> n;
int arr[n];
for (int i = 0; i < n; i++)
{
cin >> arr[i];
}
int wrapsum, totalsum = 0;
int nonwrapsum;
nonwrapsum = kadane(arr, n);
for (int i = 0; i < n; i++)
{
totalsum += arr[i];
arr[i] = -arr[i];
}
wrapsum = totalsum + kadane(arr, n);
cout << max(wrapsum, nonwrapsum) << endl;
return 0;
}
baba