2018-05-27

继续 算法导论 最大子数组问题，线性时间，这次把索引，也计算出来

思路和代码，抄袭 https://www.cnblogs.com/jimmy1989/p/8476916.html
感谢作者。
扩展-记录索引值

这里因为与代码结合着讨论的，所以下标从0开始。
这里再说一下两个自定义名词：
前最大子数组：不包含当前元素的最大子数组
边界最大子数组：只包含当前元素和不只包含当前元素，两种情况的较大值

我们以数组{1,-2,3,10,-4,7,2,-48}为例。
初始时两个索引都为0，最大子数组和边界最大子数组都是1；
当迭代索引为1时，本次值为-2，前一元素的边界最大子数组为1，所以边界最大子数组为-1，前最大子数组为1，本次迭代的最大子数组为前最大子数组，值为1，不更新索引；
当迭代索引为2时，本次值为3，前边界最大子数组为-1，所以边界最大子数组为3；前最大子数组为1，本次迭代的最大子数组为边界最大子数组，值为3；此时需要把起始索引和终止索引都更新为当前索引，即2；
当迭代索引为3是，本次值为10，前边界最大子数组为3，所以边界最大子数组为13，前最大子数组为3，本次迭代的最大子数组为边界最大子数组，值为13；此时需要把终止索引更新为当前索引，却不能更新起始索引；
…………
索引为2和索引为3的共同点在于，都是边界最大子数组大于前最大子数组，都更新了终止索引；差别在于，索引2为时，边界最大子数组只包含了索引对应的值，所以可以更新起始索引；而索引3的边界最大子数组也包含了前一元素，所以只能更新终止索引。

此时可以把需要更新索引的情况概括如下：
条件①：本次的边界最大子数组只包含当前值，且大于前最大子数组，则更新起始索引；
条件②：本次的边界最大子数组大于前最大子数组，则更新终止索引；

更新终止索引的条件②应该是充分且必要的，然而更新起始索引的条件①是充分的，确并不是必要的。考虑一下数组{4,-5,1,5}，当索引为2时，边界最大子数组为1，前最大子数组为4，只满足条件1的前半部分，然而整个数组的最大子数组的起始索引却是2。所以条件①需要进行补充。

以下是第二个版本的两个条件：
条件①：本次的边界最大子数组只包含当前值 ,

(这里说明，如果在后面出现最大子数组，那么，索引从这里开始，
这里把，另一个网站的解释，复制过来，感谢作者，允许我抄袭，引用
https://blog.csdn.net/songxueyu/article/details/47005557
“在已知A[1...j]的最大子数组的情况下，可以在线性时间内找出形如A[i..j+1]的最大子数组”
这句话里面描述的方法没有说出来.这里我先把我的结论说出来，接下来再证明。
( 由于原文中的终止索引用l ，小写的L ,容易看错，此处用zz 表示)
结论：在已知A[1...j]的最大子数组的情况下（假设A[1..j]的最大子数组是A[k...zz]），找出Ai..j+1的最大子数组是如下三个子数组中的最大和
1.A[k...zz]
2.A[k...j+1]
3.max{A[x...j+1] | x 取值范围从 zz + 2 至 j + 1}

也就是说，如果新的最大子数组不是原来的最大子数组，那么新的最大子数组的终点必然是j+1.这个是显而易见的。
假设新的最大子数组不是原来的，那么起点是哪里呢？
1.起点不可能小于k。因为如果小于k，那么说明有A[x...j+1]>A[k...j+1]（x<k)，即存在A[x...k-1]>0，这显然是不可能的。
2.起点不可能大于k小于等于zz。因为如果那样的话，说明有A[x...j+1]>A[k...j+1]（k<x<=zz），即A[k...x-1]<0，即最大子数组的起点到它中间某个点小于0，这是不可能的。
3.起点不可能位于zz+ 1，因为A[zz+1]必然小于0。)

条件②：本次的边界最大子数组大于前最大子数组 （师傅，我又发现一个更大的人参果。）
当满足条件①时，把当前索引记录为缓存索引，但并不更新起始索引；
继续干活，继续寻找
当满足条件②时，更新终止索引为当前索引，并且，更新起始索引为缓存索引。
条件②的满足总是要在条件①之后的。
条件①可能标志着一个新的开始，因为条件①可以重复满足，每次满足都应该更新缓存索引。 ，而条件②必定标志着一个结束。

# Hello World program in Python
    
print "Hello99999 World!\n"

def maxSubArray( array):

    length = len(array) 
    boundry = array[0]
    maxArray = array[0]
    # copy from https://www.cnblogs.com/jimmy1989/p/8476916.html,thank you 
    maxEndIndex = 0
    maxBeginIndex = 0
    tmpBeginIndex = 0

    for i in range(1, length):
        print '===============================>>>'+str(i)+'>>>go'
 
        if ( boundry  > 0 ):
            boundry += array[i]
            
        else:
            #now   boundry <= 0
            boundry = array[i]
            #we record  tmpBeginIndex for use 
            tmpBeginIndex=i
            
        if( maxArray < boundry ):
            maxArray = boundry
            maxEndIndex=i
            #if  boundry == array[i]:
            maxBeginIndex=tmpBeginIndex
  
    return [maxArray,maxBeginIndex,maxEndIndex]

#a=[130,-3,-250,120,-3,-16,-23,18,20,-7,12,-5,-22,15,-4,7,-99,88,12] 
a=[-13,1123,-25,8820,-3,16,-723,18,20,77,-12,-5,22,-15,-4,88,12,-789,999,8,-9,88]
#a=[1,1,1,1,1,1,1,1,-99,2,2,2,2,2,2,2,2,2,2] 
print maxSubArray(a)

result

$python main.py
Hello99999 World!

===============================>>>1>>>go
===============================>>>2>>>go
===============================>>>3>>>go
===============================>>>4>>>go
===============================>>>5>>>go
===============================>>>6>>>go
===============================>>>7>>>go
===============================>>>8>>>go
===============================>>>9>>>go
===============================>>>10>>>go
===============================>>>11>>>go
===============================>>>12>>>go
===============================>>>13>>>go
===============================>>>14>>>go
===============================>>>15>>>go
===============================>>>16>>>go
===============================>>>17>>>go
===============================>>>18>>>go
===============================>>>19>>>go
===============================>>>20>>>go
===============================>>>21>>>go
[9931, 1, 5]

木马音响积木 木马音响积木 木马音响积木 木马音响积木 木马音响积木 木马音响积木 木马音响积木 木马音响积木 木马音响积木 木马音响积木 木马音响积木 木马音响积木 木马音响积木 木马音响积木 木马音响积木 木马音响积木 木马音响积木 木马音响积木 木马音响积木 木马音响积木 木马音响积木 木马音响积木 木马音响积木 木马音响积木 木马音响积木 木马音响积木 木马音响积木 木马音响积木 木马音响积木