Skip to main content

Greedy

  • Understanding greedy
  • Solved problems are presented in alphabetical order
Gas Station

️↗ See LeetCode Problem #134​

public class Solution {    static int canCompleteCircuit(int[] gas, int[] cost) {        int n = gas.length;        int totalGas = 0;        int currentGas = 0;        int startingStation = 0;        for (int i = 0; i < n; ++i) {            totalGas += gas[i] - cost[i];            currentGas += gas[i] - cost[i];            if (currentGas < 0) {                startingStation = i + 1;                currentGas = 0;            }        }        return totalGas >= 0 ? startingStation : -1;    }    public static void main(String[] args) {        // Example 1:        int[] gas1 = {1,2,3,4,5};        int[] cost1 = {3,4,5,1,2};        //  O/P: 3        // Example 2:        int[] gas2 = {2,3,4};        int[] cost2 = {3,4,3};        //  O/P: -1        System.out.println(canCompleteCircuit(gas1, cost1));        System.out.println(canCompleteCircuit(gas2, cost2));    }}
Maximum Subarray

️↗ See LeetCode Problem #53​

public class Solution {    static int maxSubArray(int[] nums) {        int maxSum = nums[0];        int sum = nums[0];        for (int i = 1; i < nums.length; i++) {            sum = Math.max(nums[i], sum + nums[i]);            maxSum = Math.max(maxSum, sum);        }        return maxSum;   }    public static void main(String[] args) {        //  Output: 6        //  Explanation: [4,-1,2,1] has the largest sum = 6.        int[] nums1 = {-2,1,-3,4,-1,2,1,-5,4};        //  Output: 1        int[] nums2 = {1};        //  Output: 23        int[] nums3 = {5,4,-1,7,8};        maxSubArray(nums1);        maxSubArray(nums2);        maxSubArray(nums3);        System.out.println("Ex. 1: " + maxSubArray(nums1));        System.out.println("Ex. 2: " + maxSubArray(nums2));        System.out.println("Ex. 3: " + maxSubArray(nums3));    }}