package leetcode;

/**
 * https://leetcode.com/problems/gas-station/
 */
public class Problem134 {
    public int canCompleteCircuit(int[] gas, int[] cost) {
        int totalGas = 0;
        int totalCost = 0;
        for (int g : gas) {
            totalGas += g;
        }
        for (int c : cost) {
            totalCost += c;
        }
        if (totalCost > totalGas) {
            return -1;
        }
        int[] diff = new int[gas.length];
        for (int i = 0; i < gas.length; i++) {
            int g = gas[i];
            int c = cost[i];
            int x = g - c;
            diff[i] = x;
        }
        int max = Integer.MIN_VALUE;
        int maxIdx = 0;
        for (int i = 0; i < diff.length; i++) {
            int sum = 0;
            for (int j = i; j < diff.length + i; j++) {
                int k = j;
                if (k >= diff.length) {
                    k = j - diff.length;
                }
                sum += diff[k];
                if (sum < 0) {
                    break;
                }
            }
            if (sum > max) {
                max = sum;
                maxIdx = i;
            }
        }
        return maxIdx;
    }
    
    public static void main(String[] args) {
        Problem134 prob = new Problem134();
        System.out.println(prob.canCompleteCircuit(
            new int[]{1, 2, 3, 3},
            new int[]{2, 1, 5, 1}));
        System.out.println(prob.canCompleteCircuit(
            new int[] {6, 1, 4, 3, 5},
            new int[] {3, 8, 2, 4,2}));
    }
}

@@ -163,24 +163,19 @@
     int 
-totalGas
+sum
  = 0;%0A  
@@ -188,264 +188,55 @@
 int 
-totalCost = 0;%0A        for (int g : gas) %7B%0A            totalGas += g;%0A        %7D%0A        for (int c : cost) %7B%0A            totalCost += c;%0A        %7D%0A        if (totalCost %3E totalGas) %7B%0A            return -1;%0A        %7D%0A        int%5B%5D diff = new int%5Bgas.length%5D
+min = Integer.MAX_VALUE;%0A        int minIdx = 0
 ;%0A  
@@ -353,17 +353,25 @@
     int 
-x
+remaining
  = g - c
@@ -388,139 +388,25 @@
     
-diff%5Bi%5D = x;%0A        %7D%0A        int max = Integer.MIN_VALUE;%0A        int maxIdx = 0;%0A        for (int i = 0; i %3C diff.length; i++) %7B
+sum += remaining;
 %0A   
@@ -419,72 +419,20 @@
    i
-nt 
+f (
 sum 
-= 0;%0A            for (int j = i; j %3C diff.length + i; j++
+%3C min
 ) %7B%0A
@@ -451,17 +451,17 @@
     
+m
 in
-t k = j
+ = sum
 ;%0A  
@@ -478,131 +478,44 @@
     
-if (k %3E= diff.length) %7B%0A                    k = j - diff.length;%0A                %7D%0A                sum += diff%5Bk%5D;%0A        
+minIdx = i;%0A            %7D%0A        %7D%0A
     
@@ -549,539 +549,69 @@
     
-     
-   break;%0A                %7D%0A            %7D%0A            if (sum %3E max) %7B%0A                max = sum;%0A                maxIdx = i;%0A            %7D%0A        %7D%0A        
 return 
-maxIdx
+-1
 ;%0A    
-%7D%0A
     
+%7D
 %0A    
-public static void main(String%5B%5D args) %7B%0A        Problem134 prob = new Problem134();%0A        System.out.println(prob.canCompleteCircuit(%0A            new int%5B%5D%7B1, 2, 3, 3%7D,%0A            new int%5B%5D%7B2, 1, 5, 1%7D));%0A        System.out.println(prob.canCompleteCircuit(%0A            new int%5B%5D %7B6, 1, 4, 3, 5%7D,%0A            new int%5B%5D %7B3, 8, 2, 4,2%7D))
+    return (minIdx + 1) %25 gas.length
 ;%0A  

Solve problem 134