gistfile1.txt

/*
Given a sequence of heads and tails. How many significant subsequences are in this sequence, where the number of heads are not less than the number of tails?
Your standard output should be the number of subsequences.
Expected complexity: O(N*logN)
Example input:
data: [ 'H', 'T', 'H', 'T', 'T', 'H' ]
Example output:
11
*/

//http://stackoverflow.com/questions/25861012/counting-number-of-contiguous-subarrays-with-positive-sum-in-onlogn-using-on

object MyClass {

	val H = 1
	val T = -1

    def count_sequences(data: List[Int]) {
        println(mergesort(data))


    }
    
    def mergesort(data : List[Int] ) : ( List[Int], Int ) = {

    	if (data.length == 1) {
    		return ( data, 0 )
    	}

        val a = data.toArray.slice(0,data.length/2)
        val b = data.toArray.slice(data.length/2,data.length)

        val ( aSorted, aInversionCount )  = mergesort(a.toList)
        val ( bSorted, bInversonCount ) = mergesort(b.toList)

        val (result, inversionCount) = merge(aSorted, bSorted, List[Int](),aInversionCount + bInversonCount)

        return ( result, inversionCount )

    }

    def merge(a : List[Int], b : List[Int], result : List[Int], inversionCount : Int) : ( List[Int], Int )  = {

    	if (a.length == 0) {
    		return ( result ::: b, inversionCount )
    	}
    	else if (b.length == 0) {
    		return ( result ::: a, inversionCount )
    	}
    	else if (a.head > b.head) {
    		return merge(a.tail,b,result ::: List(a.head), inversionCount)
    	}
    	else {
    		return merge(a,b.tail,result ::: List(b.head), inversionCount+1)
    	}

    }

    def main(args: Array[String]) {
    	
    	val s = List[Int](H,T,H,T,T,H)

    	val sumA = s.foldLeft(List[Int]()) { (total, n) => 
    		if ( total.length > 0)  total ::: List[Int]( total.last + n) 
    		else  total ::: List[Int](n) 
    	}

    	println(sumA)

    	count_sequences(sumA)



      //count_sequences(List[Int](-44,4,1,23,2,1,6,99999))
    }
    
}