首页  |  Linux  |  C/C++  |  网络编程  |  Python   |  Algorithm  |  数据库  |  经验  |   人生 & 随想   |  站内搜索  |  关于

<<< previous

该文已被浏览1570

Kadane's Algorithm

2016-04-11

Kadane's Algorithm 用来解决这样一个问题:
在一个一维数组中,寻找连续子数组的最大和
举例来说,假如有一个一维数组为 {-2,-3,4,-1,-2,1,5,-3}, 在这个数组中连续子数组最大的和为 7, 所对应的连续子数组为 {4,-1,-2,1,5}. Kadane's Algorithm 的算法如下:
  1. 初始化两个变量 max_so_farmax_ending_here,令它们的值都为0.
  2. 遍历一维数组 arr 中的每一个元素:
    • max_ending_here += arr[i]
    • if(max_ending_here < 0)
          max_ending_here = 0
    • if(max_ending_here > max_so_far)
          max_so_far = max_ending_here
  3. 返回变量 max_so_far 的值,该值即为所求的最大和
下面是算法的具体实现(C++):
int kadane(int arr[], int len)
{
    int max_so_far = 0;
    int max_ending_here = 0;
    for(int i = 0; i < len; ++i)
    {
        max_ending_here += arr[i];
        if(max_ending_here < 0)
            max_ending_here = 0;
        else if(max_ending_here > max_so_far)
            max_so_far = max_ending_here;
    }
    return max_so_far;
}
Kadane's Algorithm有一个缺点,即不能处理全为负数的数组;如果存在数组中值全为负数的情况,则需要在执行Kadane's Algorithm之前进行事先检查,如果是全为负数,则只需输出数组中的最大值即可;或者是使用一个改进版本的 Kadane's Algorightm, 下面是一个改进版的 Kadane's Algorithm 的例子,该版本的Kadane's Algorithm可以处理全负数的情况:
int kadane(int arr[], int len)
{
	int curr_max = arr[0];
	int max_so_far = arr[0];

	for(int i = 1; i < len; ++i)
	{
		curr_max = std::max(arr[i], curr_max+arr[i]);
		max_so_far = std::max(max_so_far, curr_max);
	}

	return max_so_far;
}
另外,Kadane's Algorithm 也可以用来求解连续子数组的最小和,方法是将原数组中所有元素的正负号取反,之后再对处理后的数组调用 Kadane's Algorithm, 所得结果的相反数即为所求连续子数组的最小和。下面是一个使用该方法求解连续子数组最小和的例子:
int kadane(int arr[], int len)
{
	int curr_max = arr[0];
	int max_so_far = arr[0];

	for(int i = 1; i < len; ++i)
	{
		curr_max = std::max(arr[i], curr_max+arr[i]);
		max_so_far = std::max(max_so_far, curr_max);
	}

	return max_so_far;
}

int main()
{
	// 原数组
	int arr[] {1, 0, -6, -7, 4, 3};
	int len = sizeof(arr) / sizeof(arr[0]);

	// 符号取反后的数组
	int *invert = new int[len];
	for(int i = 0; i < len; ++i)
		invert[i] = -arr[i];

	std::cout<<-kadane(invert, len)<<"\n";
	delete [] invert;

	return 0;
}
关于 Kadane's Algorithm 更为详细的介绍可以参阅 维基百科,那里还有一个以 Python 来实现的 Kadane's Algorithm.

一如既往,如果你对文章中的内容有任何疑问,或者是发现文章中有任何错误,都可以通过下面的地址发邮件告诉我.
E-mail: rytubuntulinux@gmail.com