-
Notifications
You must be signed in to change notification settings - Fork 101
/
maximum-subarray.ts
75 lines (68 loc) · 1.87 KB
/
maximum-subarray.ts
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
import { range, reverseRange } from '../../utils';
/**
* Find the best maximum subarray crossing the mid
* Time complexity: O(n)
* @param input The input array
* @param start Start of the first array
* @param mid End of first array
* @param end End of second array
*/
export function maxCrossSubarray(
input: number[],
start: number,
mid: number,
end: number
): { start: number; end: number; sum: number } {
let leftIndex = -1;
let leftMaxSum = -Infinity;
let sum = 0;
reverseRange(mid, start).forEach(index => {
sum += input[index];
if (sum > leftMaxSum) {
leftMaxSum = sum;
leftIndex = index;
}
});
let rightIndex = -1;
let rightMaxSum = -Infinity;
sum = 0;
range(mid + 1, end).forEach(index => {
sum += input[index];
if (sum > rightMaxSum) {
rightMaxSum = sum;
rightIndex = index;
}
});
return {
start: leftIndex,
end: rightIndex,
sum: leftMaxSum + rightMaxSum,
};
}
/**
* Returns the contiguous subarray within an array of numbers which has the largest
* sum.
* Time complexity: O(n*lg(n)).
* @NOTE: there is also solution with O(n) time complexity.
* @param input The input array
* @param start Left side of the subarray
* @param end Right side of the subarray
*/
export function maxSubarray(
input: number[],
start: number,
end: number
): { start: number; end: number; sum: number } {
if (end - start === 0) return { start, end, sum: input[start] };
const mid = Math.floor((start + end) / 2);
const leftMax = maxSubarray(input, start, mid);
const rightMax = maxSubarray(input, mid + 1, end);
const crossMax = maxCrossSubarray(input, start, mid, end);
if (leftMax.sum >= rightMax.sum && leftMax.sum >= crossMax.sum) {
return leftMax;
} else if (rightMax.sum >= leftMax.sum && rightMax.sum >= crossMax.sum) {
return rightMax;
} else {
return crossMax;
}
}