小编gui*_*gis的帖子

输入:二维数组NxN - 矩阵 - 具有正负元素.

输出:任何大小的子矩阵,使得其总和是所有可能子矩阵中的最大值.

要求:算法复杂度为O(N ^ 3)

历史:在Algorithmist,Larry和Kadane算法的修改的帮助下,我设法解决了部分问题,即仅在Java中确定求和.
感谢Ernesto设法解决问题的其余部分,即确定矩阵的边界,即左上角,右下角 - 在Ruby下面.

我们希望在复杂度不大于的循环排序数组中搜索给定元素O(log n).
示例:搜索13在{5,9,13,1,3}.

我的想法是将循环数组转换为常规排序数组,然后对结果数组进行二进制搜索,但我的问题是我提出的算法是愚蠢的,它O(n)在最坏的情况下采取:

for(i = 1; i < a.length; i++){
    if (a[i] < a[i-1]){
        minIndex = i; break;
    }
}

那么第i个元素的相应索引将由以下关系确定:

(i + minInex - 1) % a.length

很明显,我的转换(从循环到常规)算法可能需要O(n),所以我们需要一个更好的.

根据ire_and_curses的想法,这是Java中的解决方案:

public int circularArraySearch(int[] a, int low, int high, int x){
    //instead of using the division op. (which surprisingly fails on big numbers)
    //we will use the unsigned right shift to get the average
    int mid = (low + high) >>> 1; …

我很抱歉删除了原来的问题,这里是:我们有一个包或一组n个整数,我们需要找到每个(n-1)个子集的乘积.例如:

S = {
1,0,3,6 } ps [1] = 0*3*6 = 0;
ps [2] = 1*3*6 = 18; 等等

经过讨论,我们需要处理这三个案例,并在下面说明如下:

1. S is a set (contains one zero element)
  for i=1 to n
    if s[i]=0
      sp[i] = s[1] * s[2] * ...* s[i-1] * s[i+1] *.....*s[n]
    else
      sp[i] = 0;

2. S is a bag (contains more than one zero element) 
  for i=1 to n
      sp[i] = 0;

3. S is a set (contains no zero elements)
   product = 1 …