C, 3mS, Maximum subarray (Kadane)


  • 0
    M

    If there is indeed a solution and it's unique, then the starting offset of the maximum subarray would give us that relevant offset.

    The problem here is about ensuring that the net available gas is always >=0. Which means we need to find that subarray sequence which helps us accumulate maximum fuel. Essentially the maximum subarray.

    Plus, in an interview setting you might just get some bonus points for illustrating Kadane.

    int canCompleteCircuit(int* gas, int gasSize, int* cost, int costSize)
    {
        int i, sum = 0, pos = 0, max_sum = 0, total_sum = 0, max_pos = 0;
    
        /* Find the maximum sub-array */
        for (i = 0; i < gasSize; ++i) {
            total_sum += gas[i] - cost[i]; // keep track of the total sum
    
            /* Kadane's algorithm */
            if (gas[i] - cost[i] + sum > gas[i] - cost[i])
                sum += gas[i] - cost[i];
            else {
                sum = gas[i] - cost[i];
                pos = i;
            }
    
            /* Keep track of maximum sub-array sum and location */
            if (sum > max_sum) {
                max_sum =  sum;
                max_pos = pos;
            }
        }
    
        /* If the maximum sub-array straddles both the ends, then update
        position. Note that "sum" is the last accumulated sub-array sum. */
        if (max_pos == 0 && max_sum + sum > max_sum)
            max_pos = pos;
        /* If we have a solution, then return the offset */
        return total_sum >= 0 ? max_pos : -1;
    }
    ``

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.