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

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

class GFG 
{ 
  	// STANDARD KADANE's ALGORITHM
    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)
// Based on KADANE's ALGORITHM

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;
    }