We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  1. Prepare
  2. Data Structures
  3. Arrays
  4. Array Manipulation
  5. Discussions

Array Manipulation

  • chrisheaney30
     + 5 comments

    Here is the solution in js in O(M+N). The key is to understand you can represent the list of N elements as a prefix sum array. Once you have the prefix array that represents the actual list, you can just scan that array to find the max sum

    function processData(input) {
    //Enter your code here
    // parse input into a friendly format to work wtih
    arr = input.split('\n'); 
    arr = arr.map(function(element){
        return element.split(' ').map(Number);
    });
    
    // initialize n and m from input array
    n = arr[0][0];
    m = arr[0][1];
    
    // create an array of length n + 1, all zeros
    container = Array(n + 1).fill(0)

    // run-time was too long when I created the container array via looping
    /*
    container = [0];
    for(var i =0; i < n; i++) container.push(0);
    */
    
    // loop through m operations and create prefix sum array
    for(var i = 1; i <= m; i++){
        //arr[i] = arr[i].split(' ').map(Number);
        container[arr[i][0]-1] += arr[i][2];
        container[arr[i][1]] -= arr[i][2];
    }
    
    max = 0;
    temp_max = 0; 
    
    // scan the prefix sum array, and then return the max sum
    for(var i = 0; i < container.length; i++){
        temp_max += container[i];
        max = Math.max(max, temp_max);
    }
    
    console.log(max);
    
}