Please help me with the approach

#1

I am not able to code a proper solution for the question. Please help me with the approach.

#2

@anurag.codingsavage This Question can be done using the brute force viz, by using two nested loops and checking the sum of every possible subset but this approach is in O(n^2). So, Now we are going to discuss an approach which solves the given problem in O(n).

Approach :
For finding the Maximum Contiguous sum we are using the kadane’s algorithm. But in the question the array is circular that means the maximum sum can be of elements which are a part of the wrapping or not. So,
There can be two cases for the maximum sum:
Case 1: The elements that contribute to the maximum sum are arranged such that no wrapping is there. Examples: {-10, 2, -1, 5}, {-2, 4, -1, 4, -1}. In this case, Kadane’s algorithm will produce the result.

Case 2: The elements which contribute to the maximum sum are arranged such that wrapping is there. Examples: {10, -12, 11}, {12, -5, 4, -8, 11}. In this case, we change wrapping to non-wrapping. Let us see how. Wrapping of contributing elements implies non wrapping of non contributing elements, so find out the sum of non contributing elements and subtract this sum from the total sum. To find out the sum of non contributing, invert sign of each element and then run Kadane’s algorithm. Our array is like a ring and we have to eliminate the maximum continuous negative that implies maximum continuous positive in the inverted arrays.

#3

I could not understand what is exactly meant by wrapping elements. Can you please explain it ?

#4

This is the solution that I have coded but it is of O(n2). Can you please suggest how to change it to O(n).

import java.util.*;
public class Main {
public static void main(String[] args) {

	Scanner sc = new Scanner(System.in);
	int sz = sc.nextInt();

	for (int i = 0; i < sz; i++) {
		int n = sc.nextInt();
		int[] arr = new int[n];
		for (int j = 0; j < n; j++) {
			arr[j] = sc.nextInt();
		}
		int ans = maximumCircularSum(arr);
		System.out.println(ans);

	}

}

public static int maximumCircularSum(int[] arr) {

	ArrayList<Integer> l = new ArrayList<>();
	for (int i = 0; i < arr.length; i++) {
		l.add(arr[i]);
	}
	for (int i = 0; i < arr.length - 1; i++) {
		l.add(arr[i]);
	}
	int ans = 0;
	for (int i = 0; i < arr.length; i++) {
		ans = Math.max(maxSubarraySum(l, i, i + arr.length - 1), ans);
	}
	return ans;
}

public static int maxSubarraySum(ArrayList<Integer> l, int start, int end) {
	int ans = 0;
	int current = 0;
	for (int i = start; i <= end; i++) {
		current = current + l.get(i);
		if (current < 0) {
			current = 0;
		}
		ans = Math.max(ans, current);
	}

	return ans;
}

}

#5

Thanks I understood the approach.

#6

I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.

On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.