[leetcode] 134 Gas Station(經典dp || 貪心)

[leetcode] 134 Gas Station(經典dp || 貪心)

（一）最容易想到的是O（n2）的解法

預處理出gas[i] - cost[i] 的數組，從每個非負的位置開始嘗試，只要能夠完成一個循環，就可以輸出結果；

對於返回-1的情況，我們經過思考和推論可以得出：對於一個循環數組，如果這個數組整體和 SUM >= 0，那麼必然可以在數組中找到這麼一個元素：從這個數組元素出發，繞數組一圈，能保證累加和一直是出於非負狀態。

所以只需要比較sum和0的大小就可以判斷是否有解。

（二）繼續對問題進行抽象，我們肯定希望一開始的路程都是加油>消耗的，這樣就可以累積油量應付後面的消耗量大的，根據這個思路，就轉變成求數組的最大連續子序列的和（並且記錄起始下標），這是我們前面接觸過的題目，例如hdu 1003；

但是因為是循環數組，我們還得考慮一種情況：就是首尾都是正數，怎麼辦呢？我們只需要再記錄並求得 最小連續子序列的和就可以了，最後取Maxsum和sum-Minsum的最大值。另外Minsum的小標要加一取余返回。

 

class Solution {
public:
    int canCompleteCircuit(vector& gas, vector& cost) {
    	int sum=0;
        for(int i=0;iMaxsum)
	          {
        		 Maxsum=tot1;
        		 Maxpos=CurMaxp;
        	  }  
        	
        	
        	if(tot2+gas[i]>gas[i])//最小連續子序列和 
	        	tot2=gas[i];
	        else
        		tot2+=gas[i];
       	    	if(tot2=(sum-Minsum))
        return Maxpos;
        else
        return (Minpos+1)%gas.size();
        
    }
};

（三）還有另外一種簡單的思路。我們首先從i站點出發，若走到當前站點cur我們的油量<0，那麼只需要從cur+1繼續出發試探即可。在此不進行證明，但是我們可以宏觀的想一下，前面的任意的前綴站點段的油量和肯定是>0的，那麼去掉任意一個前綴，只會使油量變得更少，所以我們只能嘗試從cur+1重新開始。

 

 

class Solution {
public:
    int canCompleteCircuit(vector& gas, vector& cost) {
    	int sum=0;
        for(int i=0;i