Annettuna on lista kokonaislukuja, ja tehtäväsi on laskea, monellako tavalla voit halkaista listan kahteen osaan niin, että jokainen vasemman osan alkio on pienempi kuin jokainen oikean osan alkio.

Esimerkiksi listassa [2,1,2,5,7,6,9] tapoja on 3:

• [2,1,2] ja [5,7,6,9]
• [2,1,2,5] ja [7,6,9]
• [2,1,2,5,7,6] ja [9]

Voit olettaa, että jokainen luku on välillä 1 \dots 10^9 ja listalla on enintään 10^5 lukua. Tavoitteena on, että algoritmin aikavaativuus on O(n).

Python

Toteuta tiedostoon splitlist.py funktio count, joka antaa tapojen määrän.

def count(t):
    # TODO

if __name__ == "__main__":
    print(count([1,2,3,4,5])) # 4
    print(count([5,4,3,2,1])) # 0
    print(count([2,1,2,5,7,6,9])) # 3
    print(count([1,2,3,1])) # 0

Java

Toteuta tiedostoon SplitList.java metodi count, joka antaa tapojen määrän.

public class SplitList {
    public int count(int[] t) {
        // TODO
    }

    public static void main(String[] args) {
        SplitList s = new SplitList();
        System.out.println(s.count(new int[] {1,2,3,4,5})); // 4
        System.out.println(s.count(new int[] {5,4,3,2,1})); // 0
        System.out.println(s.count(new int[] {2,1,2,5,7,6,9})); // 3
        System.out.println(s.count(new int[] {1,2,3,1})); // 0
    }
}