forked from akshitagit/JavaScript
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathmaximumCircularSubarraySum.js
More file actions
89 lines (59 loc) · 2.56 KB
/
maximumCircularSubarraySum.js
File metadata and controls
89 lines (59 loc) · 2.56 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
/*
PROBLEM STATEMENT: Given an array of n integers, you need to find the maximum subarray sum, considering the fact that the array if circular.
In other words of if the array if arr[] then next value for the i-th index is i+1 if i <n else if i==n then next index i 0
SAMPLE TEST CASES:
INPUT
[-3, 3, 5, -2, 10, -30]
OUTPUT
16
EXPLANATION {3+5-2+10} = 16, no other subarray will give better result
INPUT
[10, -3, -2, 4, -1]
OUTPUT
13
EXPLANATION {4-1+10}=13 here 4, -1, 10 is considered. P.S remember the array is circular.
*/
// SOLUTION:
// Implementation of kadane's algo
var maxSubAraySum = function(arr){
var sumSF = 0, res=0;
for(var i=0; i<arr.length; i++){
sumSF=Math.max(0, sumSF+arr[i]);
res = Math.max(res, sumSF);
}
return res;
}
var maxSubarraySumCircular = function(A) {
if(A.length==0) return 0;
const maxi = Math.max(...A);
if(maxi<=0) return maxi;
const val1 = maxSubAraySum(A);
var totalSum=0;
for(var i=0; i<A.length; i++){
totalSum += A[i];
A[i]=-1*A[i];
}
const val2 = totalSum + maxSubAraySum(A);
return Math.max(val1, val2);
};
/*
Solution Explanation:
First learn about Kadane's Algo, https://en.wikipedia.org/wiki/Maximum_subarray_problem#Kadane's_algorithm
We will be modifying the Kadane's Algo to find the maximum circular subarray sum. (mcss)
Now there are two cases:
1. The optimal subarray will be simply present in the array, without the requirement of wrapping around the ends. Example Sample test case 1
- - - - [- - - - - - - - -] - - - - -
|<-optimal array->|
2. Now the optimal subarray will be wrapper around the edges.
|- - - - - ]- - - - - - - [- - - - - - |
|left seg->| |<- right seg|
That is there will be two segments one from left another from right.
For the first case we will simply do Kadane. And store the result in val1,
For the second case if we look closely we will notice this relation
totalArray = leftSeg + MidLeftOutSeg + rightSeg
we need to find the leftSeg + rightSeg
or, leftSeg + rightSeg = totalArray - MidLeftOutSeg
So basically we need to minimize the absolute value of MidLeftOutSeg. Do we need to write another function for finding the minimum value of MidLeftOutSeg ? NO!! we will simply invert the values of the array and then again apply Kadane's Algo to get the max "inverted" sum, which is nothing but the minimum sum.
And then we will add( why add ? because we once inverted the signs and minus of minus makes plus. ) So we will val2.
Now finally we will return the max value of val1 and val2
*/