```// 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;
}```
```// Efficient Method : Time Complexity : O(n)

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

class GFG
{
static int maxEvenOdd(int arr[], int n)
{
int res = 1;
int curr = 1;

for(int i = 1; i < n; i++)
{
if((arr[i] % 2 == 0 && arr[i - 1] % 2 != 0)
||(arr[i] % 2 != 0 && arr[i - 1] % 2 == 0))
{
curr++;

res = Math.max(res, curr);
}
else
curr = 1;
}

return res;
}

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

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

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

static int maxEvenOdd(int arr[], int n)
{
int res = 1;

for(int i = 0; i < n; i++)
{
int curr = 1;

for(int j = i + 1; j < n; j++)
{
if((arr[j] % 2 == 0 && arr[j - 1] % 2 != 0)
||(arr[j] % 2 != 0 && arr[j - 1] % 2 == 0))
curr++;
else
break;
}

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

return res;
}```
```// Efficient Method (KADANE's ALGORITHM) : Time Complexity : O(n)

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

class GFG
{
static int maxSum(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;
}

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

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

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

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

for(int i = 0; i < n; i++)
{
int curr = 0;

for(int j = i; j < n; j++)
{
curr = curr + arr[j];

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

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
star

Mon Feb 07 2022 13:03:29 GMT+0000 (UTC) https://practice.geeksforgeeks.org/problems/longest-subarray-of-evens-and-odds/1/?track=DSASP-Arrays&batchId=190

#java #gfg #geeksforgeeks #lecture #arrays #subarray #kadane #longestevenoddsubarray #maximumlength
star

Mon Feb 07 2022 12:51:57 GMT+0000 (UTC) https://practice.geeksforgeeks.org/problems/kadanes-algorithm-1587115620/1/?track=DSASP-Arrays&batchId=190#

#java #gfg #geeksforgeeks #lecture #arrays #maximumsubarraysum #subarray #kadane