经典算法

Posted by Mars at

经典的算法。

1. Kadane 算法

Kadane算法,用于计算数组中连续子数组的最大或最小值。

1.1 计算连续子数组最大和、最小和

【1.求子数组最大和】

求一个非空数组A中的一个子数组SubA,使得SubA中元素的加和最大。

(子数组:在原数组中必须是连续的,长度最小为1。单个元素构成的数组和数组A本身也是A的子数组。)

Kadane算法,基于以下事实:

  • 最终求得的子数组SubA一定以数组A中某一个元素Ai作为结尾;
  • SubA在原数组A中是连续的。

假设在位置i的元素为Ai,则位置i+1的元素为Ai+1

以Ai结尾的最大加和子数组SubAi,要么只是它本身自己构成,要么是和它相连的前面若干元素一同构成。设它前面的若干元素加和为K,那么此时加和Sum(Ai)=K+Ai

如果SubAi只由自己本身构成,那么K=0。

这时考察以Ai+1结尾的子数组SubAi+1。它有两个选择:

① 继续使用Ai结尾的最大子数组,SubAi+1的加和可以表示为K+Ai+Ai+1,也就是 Sum(Ai+1)= Sum(Ai)+Ai+1

② 不继续沿用之前Ai的最大子数组,而是自己单独成为一个子数组,如果之前的子数组SubAi的加和Sum(Ai对它而言是个累赘(为负)。这时Sum(Ai+1) = Ai+1;

这两种情况的取舍,取决于二者所得子数组加和哪个更大。也就是Sum(Ai+1)=Math.max(Sum(Ai)+Ai+1, Ai+1)

因此得出Kadane算法如下:

  1. 初始化 maxSumHere = A[0]max = A[0];
  2. 对原数组A从左到右进行遍历,计算以每个数组元素位置i为结尾的子数组加和值maxSumHere,计算方法为:Sum(Ai+1)=Math.max(Sum(Ai)+Ai+1, Ai+1);
  3. 当前元素i计算完成后,更新max值。(最终结果为各个元素为结尾位置,而得到的子数组加和集的最大值。)
  4. 返回max值即为结果。
// Kadane's Algorithm
function kadanesAlgorithm(array) {
	let lastSubArrayMax = array[0];
	let totalMax = array[0];
	for(let i=1; i<array.length; i++){
        // Sum(Ai_+_1)=Math.max(Sum(A_i)+A_i_+_1, A_i_+_1);
		if(lastSubArrayMax + array[i] < array[i]) lastSubArrayMax = array[i];
		else lastSubArrayMax = lastSubArrayMax + array[i];

        // Refresh the total Max Value.
		totalMax = Math.max(lastSubArrayMax, totalMax);
	}
	return totalMax;
}

计算连续子数组的最大和或最小和问题。

// Kadane's Algorithm
// Max / Min
function kadane(arr){
    let curMax = arr[0]; // let curMin = arr[0]
    let max = arr[0];  // let min = arr[0];
    for(let i=1; i<arr.length; i++){
        curMax = Math.max(curMax+arr[i], arr[i]);  //  curMin = Math.min(curMin+arr[i], arr[i]);
        max = Math.max(max, curMax); // min = Math.min(min, curMin);
    }
    return max;
}

1.2 计算环形数组的连续子数组最大和、最小和

环形子数组的最大和

如果原数组首尾连接,那么有两种情况:

  1. 最大子数组包含首尾两个元素(覆盖了首尾连接成环的间隙);
  2. 最大子数组出现在原数组内部(不覆盖首尾连接成环的间隙)。

对于2情况,等同于一般的Kadane算法计算连续子数组最大和。

对于1情况,最大子数组包含了数组首尾连接点,则最小和一定出现在数组之中。此时最大和 = 数组全部元素和 - 最小和

环形数组

因此,可以使用Kadane算法,分别计算数组内(首尾不连接成环)的全部元素总和sum、最大和max和最小和min,然后返回sum-min和max中的最大值。

这里有一种特殊情况:当全部元素为负,min=sum,此时sum-max=0。此时max为元素中的最大值,应该返回max而非0。

var maxSubarraySumCircular = function(nums) {
    let sum = nums[0];
    let curMin = nums[0], curMax = nums[0];
    let min = curMin, max = curMax;
    for(let i=1; i<nums.length; i++){
        sum += nums[i];
        curMax = Math.max(curMax+nums[i], nums[i]);
        curMin = Math.min(curMin+nums[i], nums[i]);
        max = Math.max(max, curMax);
        min = Math.min(min, curMin);
    }
// 全部元素为负,返回max而非0.
    return max < 0 ? max : Math.max(max, sum-min);
};

1.3 计算连续子数组乘积的最大值、最小值

乘积最大子数组

乘积不同于加和,它的特点是:

  1. 如果下一个元素为正,则包含下一个元素数组的最大乘积max[i] = max[i-1] * num[i],最小乘积min[i] = min[i-1] * num[i];
  2. 如果下一个元素为负,则包含下一个元素数组的最大乘积max[i] = min[i-1] * num[i],最小乘积min[i] = max[i-1] * num[i]

因此,必须同时记录当前状态i的最大乘积max和最小乘积min,才能用于下一个状态i+1的计算。

var maxProduct = function(nums) {
    let curMax = nums[0];
    let curMin = nums[0];
    let max = curMax, min = curMin;
    for(let i=1; i<nums.length; i++){
    // 无论情况如何,乘积最大值应该是这三者中的最大者,乘积最小值应该是最小者。 
        let a1 = curMax*nums[i], a2 = curMin*nums[i], a3 = nums[i];
        curMax = Math.max(a1, a2, a3);
        curMin = Math.min(a1, a2, a3);
        max = Math.max(max, curMax);
        min = Math.min(min, curMin);
    }
    return max;
};

2. KMP算法

KMP算法,用于解决查询字符串str1中是否存在子字符串str2的问题。

2.1 算法内容

KMP

function knuthMorrisPrattAlgorithm(string, substring) {
  
	function getSuffixPosition(str){
		let suffixPosition = new Array(str.length);
		suffixPosition.fill(-1);
		let j = 0;
		for(let i=1; i<str.length; i++){
			if(str[i] === str[j])	suffixPosition[i] = j++;
			else j=0;
		}
		return suffixPosition;
	}
	
	let suffixPosition = getSuffixPosition(substring);
	
	let i=0, j=0;
	while(i < string.length){
		if(string[i] === substring[j]){
			if(j === substring.length-1) return true;
			j++; i++;
		}
		else {
			if(j === 0) i++;
			else j = suffixPosition[j-1]+1;
		}
	}
	
	return false;
}

2,2 复杂度分析

时间: O(m+n)

空间: O(m)

m为查询子串长度,n为被查询原字符串长度。

原字符串被遍历一次,查询子字符串也被遍历一次(用来建立相同前后缀的位置数组suffixPosition)。

原字符串的每次遍历,最多与子字符串执行两次比较。因此,总时间复杂度为O(2n+m) = O(m+n)

Keywords: Algorithm
previousPost
已经有 1000000 个小伙伴看完了这篇推文。