Arrays Algorithms

1. Boyer-Moore Majority Voting Algorithm
2. Kadane’s Algo

Boyer-Moore Majority Voting Algorithm

A majority element is one that appears more than nums.length / 2 times.

Algorithm Proceeding-

1. First, choose a candidate from the given set of elements
2. if it is the same as the candidate element, increase the votes. Otherwise,
   • decrease the votes if votes become 0, select another new element as the new candidate.

public static int findMajorityElement(int[] nums) {
        int majorityElement = 0;
        int count = 0;
        
        for (int num : nums) {
            if (count == 0) {
                majorityElement = num;
                count = 1;
            } else if (num == majorityElement) {
                count++;
            } else {
                count--;
            }
        }
}
        

Kadane’s Algo

Kadane’s algorithm a popular dynamic programming algorithm, it is used for finding the maximum sum of a contiguous subarray in an array. it efficiently handles both positive and negative numbers.

Conditions/Cases to remember

• does it handle empty array?[NA]
• does it handle all -ve element, i.e what will be the ans in this case, since sum of 2 -ve is grater -ve number. [YES]
• should we consider using 0 or arr[i] as substitution in code – Any works ,but corresponding initiation & iteration required.

It works by maintaining two variables:maxSoFar & maxEndingHere

1. maxSoFar stores the maximum sum of any contiguous subarray seen so far, and
2. maxEndingHere stores the maximum sum of any contiguous subarray ending at the current index.

public static int maxSubArraySum(int[] nums) {
int maxSoFar=Integer.MIN_VALUE;//final result initiated to min not 0, for cases where elements with -ve numbers would result in max being 0 -which is incorrect.
        int maxEndingHere=0;
        for(int i=0;i<nums.length;i++){
            maxEndingHere=Math.max(nums[i]+maxEndingHere,nums[i]);
            maxSoFar=Math.max(maxSoFar,maxEndingHere);
        }
      return maxSoFar;  
}