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
    }
}