-6

I have some numbers at the input:

1 1 7 3 2 0 0 4 5 5 6 2 1

And I look for a longest monotonic subsequence and what is the sum of this subsequence. The result is:

6 20

I cannot find the algorithm at the internet. Do you own/found one? This is about longest monotonic not longest increasing subsequence.

Definition of monotonic: http://en.wikipedia.org/wiki/Monotonic_function

I know that someone will ask: What have you tried? So i tried writing it(please don't check it I only post it so no one asks that question above I look for different algorithm->optimal one)

import java.io.BufferedReader;
import java.io.InputStreamReader;

public class Rozwiazanie {
    public static void main(String[] args) {
        try {
            BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

            //2^63 > 10^16 = 10^7 * 10^9 longi starcza
            //10^9 inty starcza
            //int 32 bity, long 64 bity
            long podsuma = 0;
            int dlugosc = 0;
            int maxDlugosc = 0;
            long maxPodsuma = 0;
            int poczatekRownych = 0;
            int poprzedniWyraz = 0, aktualnyWyraz;//uwaga jakby cos nie gralo w sprawdzarce zmien typ na long
            boolean czyRosnacy = false, rowny = false;
            String[] splittedLinia = br.readLine().split((char) 32 + "");//moglaby byc " " ale tak na wszelki wypadek nie ma chuja zeby sie popierdolilo teraz nawet na linuxie
            for (int i = 0; i < splittedLinia.length; i++) {
                if (i == 0) {
                    aktualnyWyraz = Integer.parseInt(splittedLinia[0]);
                    maxDlugosc = dlugosc = 1;
                    maxPodsuma = podsuma = aktualnyWyraz;
                    if (splittedLinia.length > 1) {
                        int nastepnyWyraz = Integer.parseInt(splittedLinia[1]);
                        czyRosnacy = nastepnyWyraz > aktualnyWyraz;
                        rowny = nastepnyWyraz == aktualnyWyraz;
                    }
                    System.out.println("akt: " + aktualnyWyraz + " pop: " + poprzedniWyraz + " dlugosc: " + dlugosc + " " + 1);
                } else {
                    aktualnyWyraz = Integer.parseInt(splittedLinia[i]);
                    System.out.println(rowny);
                    if (aktualnyWyraz == poprzedniWyraz && rowny) {
                        podsuma += aktualnyWyraz;
                        dlugosc++;
                        System.out.println("akt: " + aktualnyWyraz + " pop: " + poprzedniWyraz + " dlugosc: " + dlugosc + " " + 2);
                    } else if (rowny) {
                        rowny = false;
                        czyRosnacy = aktualnyWyraz > poprzedniWyraz;
                        System.out.println("akt: " + aktualnyWyraz + " pop: " + poprzedniWyraz + " dlugosc: " + dlugosc + " " + 3);
                    }

                    if (!rowny) {

                        if (aktualnyWyraz >= poprzedniWyraz && czyRosnacy) {
                            podsuma += aktualnyWyraz;
                            dlugosc++;
                            System.out.println("akt:" + aktualnyWyraz + " pop: " + poprzedniWyraz + " dlugosc: " + dlugosc + " " + 4);
                        } else if (aktualnyWyraz <= poprzedniWyraz && !czyRosnacy) {
                            podsuma += aktualnyWyraz;
                            dlugosc++;
                            System.out.println("akt: " + aktualnyWyraz + " pop: " + poprzedniWyraz + " dlugosc: " + dlugosc + " " + 5);
                        } else {
                            //  if (aktualnyWyraz == poprzedniWyraz) {
                            rowny = true;
                            //  } else {
                            if (maxDlugosc < dlugosc) {
                                maxDlugosc = dlugosc;
                                maxPodsuma = podsuma;

                            }
                            podsuma = poprzedniWyraz + aktualnyWyraz;
                            dlugosc = 2;
                            czyRosnacy = aktualnyWyraz > poprzedniWyraz;
                            rowny = aktualnyWyraz == poprzedniWyraz;
                            System.out.println("akt: " + aktualnyWyraz + " pop: " + poprzedniWyraz + " dlugosc: " + dlugosc + " " + 6);
                            //}
                        }
                    }
                }
                poprzedniWyraz = aktualnyWyraz;
            }
            System.out.println(maxDlugosc + " " + maxPodsuma);
        } catch (Exception e) {
            e.printStackTrace();
        }
    }
}
//65 87 47 5 12 74 25 32 78 44 40 77 85 4 29 57:
4

1 回答 1

1

试试这个：

import java.io.BufferedReader;
import java.io.InputStreamReader;

public class Rozwiazanie {
    public static void main(String[] args) {
        try {
            BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
            String[] splittedLinia = br.readLine().split((char) 32 + "");//moglaby byc " " ale tak na wszelki wypadek nie ma chuja zeby sie popierdolilo teraz nawet na linuxie
            int aktualnyWyraz = Integer.parseInt(splittedLinia[0]);//uwaga jakby cos nie gralo w sprawdzarce zmien typ na long
            int poprzedniWyraz = 0; 

            long podsumaRosnaca = aktualnyWyraz;
            long podsumaSpadajaca = aktualnyWyraz;

            int dlugoscRosnaca = 1;
            int dlugoscSpadajaca = 1;

            int maxDlugosc = 1;
            long maxPodsuma = aktualnyWyraz;

            int czyRosnacy = 0; // 0 -- nie znane (jezeli w poczatku wszystkie liczby sa rowne), 1 -- rosnacy, -1 -- spadajacy
            boolean rowny = false;
            System.out.println("akt: " + aktualnyWyraz + " dlR: " + dlugoscRosnaca + " podsumaR: " + podsumaRosnaca + " dlP: " + dlugoscSpadajaca + " podsumaP: " + podsumaSpadajaca);

            for (int i = 1; i < splittedLinia.length; i++) {
                poprzedniWyraz = aktualnyWyraz;
                aktualnyWyraz = Integer.parseInt(splittedLinia[i]);
                if (aktualnyWyraz == poprzedniWyraz) {
                    podsumaRosnaca += aktualnyWyraz;
                    podsumaSpadajaca += aktualnyWyraz;
                    dlugoscRosnaca++;
                    dlugoscSpadajaca++;
                    rowny = true;
                } else { // rozne liczby
                    if (aktualnyWyraz > poprzedniWyraz) { // rosnie
                        podsumaRosnaca += aktualnyWyraz;
                        dlugoscRosnaca++;      

                        if (rowny) {
                            dlugoscSpadajaca = 1;
                            podsumaSpadajaca = 0;
                            rowny = false;
                        }       
                        if (czyRosnacy < 0) {
                            if (dlugoscSpadajaca > maxDlugosc) {
                                maxDlugosc = dlugoscSpadajaca;
                                maxPodsuma = podsumaSpadajaca;
                            }
                            podsumaSpadajaca = 0;
                            dlugoscSpadajaca = 1;
                        }
                        czyRosnacy = 1;   
                    } else { // spada
                        podsumaSpadajaca += aktualnyWyraz;
                        dlugoscSpadajaca++; 

                        if (rowny) {
                            dlugoscRosnaca = 1;
                            podsumaRosnaca = 0;
                            rowny = false;
                        }
                        if (czyRosnacy == 1) {
                            if (dlugoscRosnaca > maxDlugosc) {
                                maxDlugosc = dlugoscRosnaca;
                                maxPodsuma = podsumaRosnaca;
                            }
                            podsumaRosnaca = 0;
                            dlugoscRosnaca = 1;
                        }  
                        czyRosnacy = -1;
                    }

                }
                System.out.println("akt: " + aktualnyWyraz + " dlR: " + dlugoscRosnaca + " podsumaR: " + podsumaRosnaca + " dlP: " + dlugoscSpadajaca + " podsumaP: " + podsumaSpadajaca);
            }


            System.out.println("maxDlugosc " + maxDlugosc + " maxPodsuma " + maxPodsuma);
        } catch (Exception e) {
            e.printStackTrace();
        }
    }
}

我必须改变的：

  • 您需要一个计数器 [dlugosc] (+ sum [podsuma]) 用于升序 [rosnacy] 和降序 [spadajacy] 值，因为当值相同 [rowny] 时，您需要计算这两个值。
  • 我将 boolean "rowny" [equal] 更改为 int，因为我认为可能有 3 个值：升序、降序或未知。如果一开始有几个相等的值，那么总是“未知”。
  • 该程序至少需要一个数字，但因此您无需检查循环的每次迭代是否 i == 0。
  • 通过这些数字，我必须检查几件事，最重要的是，实际值 [aktualnyWyraz] 和最后使用的值 [poprzedniWyraz] 是否相同（然后必须更改所有计数器和总和）或不同。不同可能意味着升序或降序，因此我们必须递增相关计数器并将相关总和相加。“相反”的变量会发生什么？好吧，我们需要检查计数器是否大于最大值（所以这些值可能对结果有用），然后将它们设置回开始。
于 2013-11-15T14:09:48.043 回答