-
Notifications
You must be signed in to change notification settings - Fork 2
/
Copy pathmax-sub-array-sum.js
114 lines (110 loc) · 4.93 KB
/
max-sub-array-sum.js
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
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
// Write a function called maxSubarraySum which accepts an array of Integers and a number called N.
// The function should calculate the maximum sum of N **Consecutive** elements in the array.
console.log("--------------------- Method 1: Basic ----------------------");
const maxSubarraySum = (inputArr, subArrEle) => {
const fnStartTime = Date.now();
// validations
if (!inputArr) {
return "ERROR: Input sorted array is required";
}
if (!Array.isArray(inputArr)) {
return `ERROR: Input parameter should be sorted array only currently it is ${typeof inputArr}`;
}
console.log("inputArr length:", inputArr?.length);
let result = 0;
let totalLoopRuns = 0;
for (let i = 0; i < inputArr.length - subArrEle + 1; i++) {
let subArrEleSum = 0;
totalLoopRuns++;
for (let j = i; j < i + subArrEle; j++) {
totalLoopRuns++;
subArrEleSum += inputArr[j];
}
result = result < subArrEleSum ? subArrEleSum : result;
}
console.log("totalLoopRuns:", totalLoopRuns);
const fnEndTime = Date.now();
console.log("Total Time Taken:", fnEndTime - fnStartTime);
console.log("result:", result);
console.log("<------------------------------------------------->");
return "";
};
console.log(
maxSubarraySum(
[
1, 2, 5, 2, 8, 1, 5, 1, 2, 1, 2, 4, 5, 14, 0, 1, 2, 5, 2, 8, 1, 5, 1, 2,
1, 2, 4, 5, 14, 0, 1, 2, 5, 2, 8, 1, 5, 1, 2, 1, 2, 4, 5, 14, 0, 1, 2, 5,
2, 8, 1, 5, 1, 2, 1, 2, 4, 5, 14, 0, 1, 2, 5, 2, 8, 1, 5, 1, 2, 1, 2, 4,
5, 14, 0, 1, 2, 5, 2, 8, 1, 5, 1, 2, 1, 2, 4, 5, 14, 0, 1, 2, 5, 2, 8, 1,
5, 1, 2, 1, 2, 4, 5, 14, 0, 1, 2, 5, 2, 8, 1, 5, 1, 2, 1, 2, 4, 5, 14, 0,
1, 2, 5, 2, 8, 1, 5, 1, 2, 1, 2, 4, 5, 14, 0, 1, 2, 5, 2, 8, 1, 5, 1, 2,
1, 2, 4, 5, 14, 0, 1, 2, 5, 2, 8, 1, 5, 1, 2, 1, 2, 4, 5, 14, 0, 1, 2, 5,
2, 8, 1, 5, 1, 2, 1, 2, 4, 5, 14, 0, 1, 2, 5, 2, 8, 1, 5, 1, 2, 1, 2, 4,
5, 14, 0, 1, 2, 5, 2, 8, 1, 5, 1, 2, 1, 2, 4, 5, 14, 0, 1, 2, 5, 2, 8, 1,
5, 1, 2, 1, 2, 4, 5, 14, 0, 1, 2, 5, 2, 8, 1, 5, 1, 2, 1, 2, 4, 5, 14, 0,
],
2
)
); // 19
console.log(maxSubarraySum([1, 2, 5, 2, 8, 1, 5], 4)); // 17
console.log(maxSubarraySum([4, 2, 1, 6], 1)); // 6
console.log(maxSubarraySum("Sanjay")); // error
console.log(maxSubarraySum()); // error
console.log("--------------------- Method 2: Optimized ----------------------");
const maxSubarraySum2 = (inputArr, subArrEle) => {
// validations
if (!inputArr) {
return "Input sorted array is required";
}
if (!Array.isArray(inputArr)) {
return `Input parameter should be sorted array only currently it is ${typeof inputArr}`;
}
console.log("inputArr length:", inputArr?.length);
let maxSum = 0;
let totalLoopRuns = 0;
let arrEleSum = 0;
// first subEleSum
for (let i = 0; i < subArrEle; i++) {
maxSum += inputArr[i];
totalLoopRuns++;
}
arrEleSum = maxSum;
for (let j = subArrEle; j < inputArr.length; j++) {
const sumWithNext = Number(arrEleSum) + Number(inputArr[j]);
// console.log('sumWithNext',sumWithNext)
const currentSubArrEleSum =
Number(sumWithNext) - Number(inputArr[j - subArrEle]);
// console.log('currentSubArrEleSum',currentSubArrEleSum)
arrEleSum = currentSubArrEleSum;
maxSum = maxSum < currentSubArrEleSum ? currentSubArrEleSum : maxSum;
// console.log('maxSum',maxSum)
// console.log('..........................')
totalLoopRuns++;
}
console.log("totalLoopRuns:", totalLoopRuns);
console.log("result:", maxSum);
console.log("<------------------------------------------------->");
return "";
};
console.log(maxSubarraySum2([1, 2, 5, 2, 8, 1, 5], 2)); // 10
console.log(
maxSubarraySum2(
[
1, 2, 5, 2, 8, 1, 5, 1, 2, 1, 2, 4, 5, 14, 0, 1, 2, 5, 2, 8, 1, 5, 1, 2,
1, 2, 4, 5, 14, 0, 1, 2, 5, 2, 8, 1, 5, 1, 2, 1, 2, 4, 5, 14, 0, 1, 2, 5,
2, 8, 1, 5, 1, 2, 1, 2, 4, 5, 14, 0, 1, 2, 5, 2, 8, 1, 5, 1, 2, 1, 2, 4,
5, 14, 0, 1, 2, 5, 2, 8, 1, 5, 1, 2, 1, 2, 4, 5, 14, 0, 1, 2, 5, 2, 8, 1,
5, 1, 2, 1, 2, 4, 5, 14, 0, 1, 2, 5, 2, 8, 1, 5, 1, 2, 1, 2, 4, 5, 14, 0,
1, 2, 5, 2, 8, 1, 5, 1, 2, 1, 2, 4, 5, 14, 0, 1, 2, 5, 2, 8, 1, 5, 1, 2,
1, 2, 4, 5, 14, 0, 1, 2, 5, 2, 8, 1, 5, 1, 2, 1, 2, 4, 5, 14, 0, 1, 2, 5,
2, 8, 1, 5, 1, 2, 1, 2, 4, 5, 14, 0, 1, 2, 5, 2, 8, 1, 5, 1, 2, 1, 2, 4,
5, 14, 0, 1, 2, 5, 2, 8, 1, 5, 1, 2, 1, 2, 4, 5, 14, 0, 1, 2, 5, 2, 8, 1,
5, 1, 2, 1, 2, 4, 5, 14, 0, 1, 2, 5, 2, 8, 1, 5, 1, 2, 1, 2, 4, 5, 14, 0,
],
2
)
); // 19
console.log(maxSubarraySum2([1, 2, 5, 2, 8, 1, 5], 4)); // 17
console.log(maxSubarraySum2([4, 2, 1, 6], 1)); // 6
console.log(maxSubarraySum2("Sanjay")); // error
console.log(maxSubarraySum2()); // error