```// Efficient Method (Based on KADANE's ALGORITHM) : Time Complexity : O(n)

import java.util.*;
import java.io.*;

class GFG
{
static int normalMaxSum(int arr[], int n)
{
int res = arr[0];

int maxEnding = arr[0];

for(int i = 1; i < n; i++)
{
maxEnding = Math.max(maxEnding + arr[i], arr[i]);

res = Math.max(maxEnding, res);
}

return res;
}

static int overallMaxSum(int arr[], int n)
{
// Normal Sum
int max_normal = normalMaxSum(arr, n);

if(max_normal < 0)
return max_normal;

int arr_sum = 0;
// Circular Sum
for(int i = 0; i < n; i++)
{
arr_sum += arr[i];

arr[i] = -arr[i];
}

int max_circular = arr_sum + normalMaxSum(arr, n);

return Math.max(max_circular, max_normal);
}

public static void main(String args[])
{
int arr[] = {8, -4, 3, -5, 4}, n = 5;

System.out.println(overallMaxSum(arr, n));
}
}

// Naive Method : Time Complexity : O(n^2)

static int maxCircularSum(int arr[], int n)
{
int res = arr[0];

for(int i = 0; i < n; i++)
{
int curr_max = arr[i];
int curr_sum = arr[i];

for(int j = 1; j < n; j++)
{
int index = (i + j) % n;

curr_sum += arr[index];

curr_max = Math.max(curr_max, curr_sum);
}

res = Math.max(res, curr_max);
}
return res;
}```
star

Mon Feb 07 2022 13:18:10 GMT+0000 (UTC) https://practice.geeksforgeeks.org/problems/max-circular-subarray-sum-1587115620/1/?track=DSASP-Arrays&batchId=190

#java #gfg #geeksforgeeks #lecture #arrays #subarray #kadane #circularsubarray #subarraysum #maximumsum