Menu
I have a program to determine the largest contiguous sum in an array, but want to extend it to work with circular arrays. Is there an easier way to do that than doubling the single array and calling my function to find the largest sum over all n-length arrays in the 2n length array?
815
Maximum Sum Circular Subarray. Given a circular integer array nums of length n , return the maximum possible sum of a non-empty subarray of nums . A circular array means the end of the array connects to the beginning of the array.
It can be a single element of an array or some fraction of the array. The largest sum contiguous subarray means a subarray that has the maximum sum value. For example, an array is {-10, 5, 1, 6, -9, 2, -7, 3, -5}. Its sub arrays can be: {-10,5,1,6} or {5,1,6} or {2,7,3, -5} etc.
Simple Approach: Run a loop for i from 0 to n – 1, where n is the size of the array. Now, we will run a nested loop for j from i to n – 1 and add the value of the element at index j to a variable currentMax. Lastly, for every subarray, we will check if the currentMax is the maximum sum of all contiguous subarrays.
A contiguous subarray is simply a subarray of an array with a condition that the elements of the subarray should be in exact sequence as the sequence of the elements in the array.
See the following link :
It solves a problem using Kadane Algorithem.
http://www.geeksforgeeks.org/maximum-contiguous-circular-sum/
98
I think the solution by @spinning_plate is wrong. Ca you please test it for the given cases.
int arr[] = {-3, 6, 2, 1, 7, -8, 13, 0};
Your approach returns 21.
Actual solution can be start from 6th index(i.e. 13 value) .. and end to 4th index(i.e. 7 value). Since array is circular we can take continuous series from 6th index to 7th index and from 0th index to 4th index.
The actual answer for the above case is : 26
43
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
