//Scala Proejct will start from main
def main
( args
: Array
[ String
] ) { println( getLongestLists( getPossibleSequenceLists( List( 19 ,3 ,11 ,7 ,15 ,12 ,4 ,12 ,8 ,16 ) ) ) ) ;
}
// return all of possible sequence lists which have any length from input numbers
// it uses dynamic programming ways which means that it starts to big problem from small one to solve the problem
def getPossibleSequenceLists
( xs
: List
[ Int
] ) : List
[ List
[ Int
] ] = { List( xs)
getPossibleSequenceLists( xs.init ) ++getAddedLists( getPossibleSequenceLists( xs.init ) , xs.last )
/* Last result have all possible result except next inputs,
the next input comes in last result,
then some lists should be added from getAddedLists method
*/
}
// return max size from list of lists
def max
( xs
: List
[ List
[ Int
] ] ) : Int
= xs
match { case List
( x
: List
[ Int
] ) => x.
size case x
:: y
:: rest
=> max
( ( if ( x.
size > y.
size ) x
else y
) :: rest
) }
/* There are two input values in this function
xs = list of the possible sequence lists
i = next continuous value
For example,
x =
(1,2)
(3)
(6),
i = 4,
then output is (1,2,4), (3,4), (4)
*/
def getAddedLists
( xs
: List
[ List
[ Int
] ] , i
: Int
) : List
[ List
[ Int
] ] = { List( List( i) )
getAddedLists( xs.init , i) ++List( ( xs.last ++List( i) ) )
getAddedLists( xs.init , i)
}
/*
* return list of sequences which have the longest length
* it performs after the possible list of possible sequences which have any length of it.
*/
def getLongestLists
( xs
: List
[ List
[ Int
] ] ) : List
[ List
[ Int
] ] = { List( xs.head )
if ( xs.
last .
size > max
( xs.
init ) ) List( xs.last )
if ( xs.
last .
size == max
( xs.
init ) ) List( xs.last ) ++getLongestLists( xs.init )
getLongestLists( xs.init )
}
}
b2JqZWN0IENvbnRpZ2lvdXNOdW1iZXIgewogIAogIAoJLy9TY2FsYSBQcm9lamN0IHdpbGwgc3RhcnQgZnJvbSBtYWluCglkZWYgbWFpbihhcmdzOiBBcnJheVtTdHJpbmddKXsKCQlwcmludGxuKGdldExvbmdlc3RMaXN0cyhnZXRQb3NzaWJsZVNlcXVlbmNlTGlzdHMoTGlzdCgxOSwzLDExLDcsMTUsMTIsNCwxMiw4LDE2KSkpKTsKCgoJfQoJLy8gcmV0dXJuIGFsbCBvZiBwb3NzaWJsZSBzZXF1ZW5jZSBsaXN0cyB3aGljaCBoYXZlIGFueSBsZW5ndGggZnJvbSBpbnB1dCBudW1iZXJzCgkvLyBpdCB1c2VzIGR5bmFtaWMgcHJvZ3JhbW1pbmcgd2F5cyB3aGljaCBtZWFucyB0aGF0IGl0IHN0YXJ0cyB0byBiaWcgcHJvYmxlbSBmcm9tIHNtYWxsIG9uZSB0byBzb2x2ZSB0aGUgcHJvYmxlbQoJZGVmIGdldFBvc3NpYmxlU2VxdWVuY2VMaXN0cyh4czpMaXN0W0ludF0pIDogTGlzdFtMaXN0W0ludF1dID0gewoJCQlpZih4cy5zaXplID09IDEpCgkJCQlMaXN0KHhzKQoJCQkJZWxzZQoJCQkJCWdldFBvc3NpYmxlU2VxdWVuY2VMaXN0cyh4cy5pbml0KSsrZ2V0QWRkZWRMaXN0cyhnZXRQb3NzaWJsZVNlcXVlbmNlTGlzdHMoeHMuaW5pdCksIHhzLmxhc3QpIAoJCQkJCS8qIExhc3QgcmVzdWx0IGhhdmUgYWxsIHBvc3NpYmxlIHJlc3VsdCBleGNlcHQgbmV4dCBpbnB1dHMsCgkJCQkJdGhlIG5leHQgaW5wdXQgY29tZXMgaW4gbGFzdCByZXN1bHQsCgkJCQkJdGhlbiBzb21lIGxpc3RzIHNob3VsZCBiZSBhZGRlZCBmcm9tIGdldEFkZGVkTGlzdHMgbWV0aG9kIAoJCQkJCQoJCQkJCSovCgl9CgoJCgkvLyByZXR1cm4gbWF4IHNpemUgZnJvbSBsaXN0IG9mIGxpc3RzCglkZWYgbWF4KHhzOiBMaXN0W0xpc3RbSW50XV0pOiBJbnQgPSB4cyBtYXRjaCB7CgljYXNlIE5pbCA9PiAtMQoJY2FzZSBMaXN0KHg6IExpc3RbSW50XSkgPT4geC5zaXplCgljYXNlIHggOjogeSA6OiByZXN0ID0+IG1heCggKGlmICh4LnNpemUgPiB5LnNpemUpIHggZWxzZSB5KSA6OiByZXN0ICkKCX0gCgoJCgkvKiBUaGVyZSBhcmUgdHdvIGlucHV0IHZhbHVlcyBpbiB0aGlzIGZ1bmN0aW9uCgkJeHMgPSBsaXN0IG9mIHRoZSBwb3NzaWJsZSBzZXF1ZW5jZSBsaXN0cyAKCQlpICA9IG5leHQgY29udGludW91cyB2YWx1ZQoJCUZvciBleGFtcGxlLAoJCXggPQoJCSgxLDIpCgkJKDMpCgkJKDYpLAoJCWkgPSA0LAoJCXRoZW4gb3V0cHV0IGlzICgxLDIsNCksICgzLDQpLCAoNCkKCQkgCgkqLwoJZGVmIGdldEFkZGVkTGlzdHMoeHM6TGlzdFtMaXN0W0ludF1dLCBpOkludCkgOiBMaXN0W0xpc3RbSW50XV0gPSB7CgkJCWlmKHhzLnNpemUgPT0gMCkKCQkJCUxpc3QoTGlzdChpKSkKCQkJCWVsc2UKCQkJCQlpZiggeHMubGFzdC5sYXN0IDwgaSkKCQkJCQkJZ2V0QWRkZWRMaXN0cyh4cy5pbml0LCBpKSsrTGlzdCgoeHMubGFzdCsrTGlzdChpKSkpCgkJCQkJCWVsc2UKCQkJCQkJCWdldEFkZGVkTGlzdHMoeHMuaW5pdCwgaSkKCgl9CgoJLyoKCSAqIHJldHVybiBsaXN0IG9mIHNlcXVlbmNlcyB3aGljaCBoYXZlIHRoZSBsb25nZXN0IGxlbmd0aAoJICogaXQgcGVyZm9ybXMgYWZ0ZXIgdGhlIHBvc3NpYmxlIGxpc3Qgb2YgcG9zc2libGUgc2VxdWVuY2VzIHdoaWNoIGhhdmUgYW55IGxlbmd0aCBvZiBpdC4KCSAqLwoJZGVmIGdldExvbmdlc3RMaXN0cyh4czpMaXN0W0xpc3RbSW50XV0pIDogTGlzdFtMaXN0W0ludF1dID0gewoJCQlpZih4cy5zaXplID09IDEpCgkJCQlMaXN0KHhzLmhlYWQpCgkJCQllbHNlCgkJCQkJaWYoeHMubGFzdC5zaXplID4gbWF4KHhzLmluaXQpKQoJCQkJCQlMaXN0KHhzLmxhc3QpCgkJCQkJCWVsc2UKCQkJCQkJCWlmKHhzLmxhc3Quc2l6ZSA9PSBtYXgoeHMuaW5pdCkpCgkJCQkJCQkJTGlzdCh4cy5sYXN0KSsrZ2V0TG9uZ2VzdExpc3RzKHhzLmluaXQpCgkJCQkJCQkJZWxzZQoJCQkJCQkJCQlnZXRMb25nZXN0TGlzdHMoeHMuaW5pdCkKCX0JCn0=