用递归吧，分治策略，求最大子数组

//: Playground - noun: a place where people can play

import UIKit

var str = "Hello,playground"
var A = [13,-3,-25,20,-16,-23,18,-7,12,-5,-22,15,-4,7]
for i in 0..<A.count {
    print(A[i])
    
}

func FINDMAXCROSSINGSUBARRAY(A:[Int],low:Int,mid:Int,high:Int)->(maxleft:Int,maxright:Int,lr:Int){
    var sum = 0
    var maxleft = 0
    var maxright = 0
    var left_sum = -1000;
    for i in stride(from: mid,through: low,by: -1)  {
        sum = A[i] + sum
        if(sum > left_sum)
        {
            left_sum = sum
            maxleft = i
        }
        
    }
    var right_sum = -1000
    sum = 0
    for j in mid+1...high
    {
        sum += A[j]
        if(sum > right_sum)
        {
            right_sum = sum
            maxright = j
        }
    }
    
    return(maxleft,maxright,left_sum+right_sum)
    
}

func FINDMAXIMUMSUBARRAY(A:[Int],high:Int) ->(l:Int,h:Int,zhi:Int)
{
    if (high == low) {
        return (low,high,A[low])
    }
    else {
        let mid = (low+high)/2
        let a = FINDMAXIMUMSUBARRAY(A: A,low: low,high: mid)    
        let b = FINDMAXIMUMSUBARRAY(A: A,low: mid+1,high: high)
        let c = FINDMAXCROSSINGSUBARRAY(A: A,mid: mid,high: high)
        if(a.zhi >= b.zhi && a.zhi >= c.lr)
        {return (a.l,a.h,a.zhi)}
        else if (b.zhi >= a.zhi && b.zhi >= c.lr)
        { return (a.l,b.h,b.zhi)}
        else {return (c.maxleft,c.maxright,c.lr)}
    }
}

FINDMAXIMUMSUBARRAY(A: A,low: 0,high: A.count-1)