algorithm-practice/namaste-dev/30DayDSAChallenge/maxSubArray.js at main · amit265/algorithm-practice · GitHub

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
// find the contiguous subarrray with the largest sum
// a subarray must contain consecutive elements

// kadane's algorithm

// input array ----> [-2, 1, -3, 4, -1, 2, 1, -5, 4]
// output array ---> [-2, 1, -3, //4, -1, 2, 1//, -5, 4]  ---> [4, -1, 2, 1]

// sum = 6


// 1. keep adding numbsers to current Sum;

// 2. track the maximum sum seen so far

// 3. if current sum becomes negative, reset it to 0

// time O(n)
// space O(1)

const nums = [-2, 1, -3, 4, -1, 2, 1, -5, 4];
function maxSubArray(nums){
    let currentSum = 0;
    let maxSum = nums[0];

    for(let num of nums){
        currentSum += num;

        maxSum = Math.max(maxSum, currentSum);

        if(currentSum < 0){
            currentSum = 0
        }
    }

    return maxSum;
}


console.log(maxSubArray(nums));


// brute force

// function maxSubarray(nums){
//     let maxSum = -Infinity;

//     for(let i = 0; i< nums.length; i++) {
//         let currentSum  = 0;
//         for(let j = i ; j < nums.length; j++){
//             currentSum += nums[j];
//             maxSum = Math.max(maxSum, currentSum);
//         }
//     }

//     return maxSum;
// }

// console.log(maxSubarray([-2, 1, -3, 4, -1, 2, 1, -5, 4]))