0
\$\begingroup\$

How can I make this program run faster? On enter, I have a string from the console. For example:

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

On exit, it will be

6 20

Could you recommend a way to make this run faster?

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.StringTokenizer;
public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String line;
        ArrayList<Integer> _arr = new ArrayList<Integer>();
        while((line=br.readLine())!= null){
                StringTokenizer tok = new  StringTokenizer(line);
                while (tok.hasMoreTokens()) {
                    _arr.add((Integer.parseInt(tok.nextToken())));
                }
            }
        Algorithm(_arr);
    }
    private static void Algorithm(ArrayList<Integer> arr) {
        int ascLength = 1,
            descLength = 1,
            ascSequenceStart = 0,
            descSequenceStart = 0,
            ascLongest = 1,
            descLongest = 1,
            summa = 0,
            tmp1, tmp2;
        for (int i = 1; i<arr.size(); i++) {
            tmp1 = arr.get(i-1);
            tmp2 = arr.get(i);
            if(tmp2>tmp1){
                ascLength++;
                descLength = 1;
            } else if (tmp2<tmp1) {
                descLength++;
                ascLength = 1;
            } else if (tmp1==tmp2){
                descLength++;
                ascLength++;
            }
            if (ascLength > ascLongest) {
                ascLongest = ascLength;
                ascSequenceStart = i - ascLength + 1;
            }
            if (descLength > descLongest) {
                descLongest = descLength;
                descSequenceStart = i - descLength + 1;
            }
        }
        if (ascLongest > descLongest) {
            for (int i = ascSequenceStart; i < (ascSequenceStart+ascLongest); i++) {
                summa += arr.get(i);
            }
            System.out.print(String.valueOf(ascLongest)+" "+String.valueOf(summa));
        } else {
             for (int i = descSequenceStart; i < (descSequenceStart+descLongest); i++) {
                 summa += arr.get(i);
             }
             System.out.print(String.valueOf(descLongest)+" "+String.valueOf(summa));
        }
    }
}
\$\endgroup\$
  • 4
    \$\begingroup\$ Welcome to Code Review! Can you please describe what the program does? \$\endgroup\$ – Kevin Nov 15 '13 at 0:21
  • \$\begingroup\$ @Kevin: I wasn't sure how to edit the title, so hopefully this is good enough until more details are given. \$\endgroup\$ – Jamal Nov 15 '13 at 0:39
  • \$\begingroup\$ What's the assignment? What is the intended purpose of this? How come '1 1 7 3 2 0 0 4 5 5 6 2 1' turns into '6 20' ? \$\endgroup\$ – Max Nov 15 '13 at 9:26
3
\$\begingroup\$

Yeah, without giving too much away (this is obviously homework)....

First though, the assumption I make is that the assignment is:

  1. find the length of the longest series of either increasing, or decreasing numbers
  2. sum the values in this longest sequence.

There are two parts to this problem as well. The first part is getting the user input, and the second is identifying and processing the sequences. I will assume that you can process the user input adequately, and put it in an array of integer int[] values = .... You use an ArrayList<Integer> which is not, in my opinion, a great container for doing arithmetic on...

This problem can be solved by managing three variables, and keeping a maxlen and maxsum total.

First you need to ensure you have at least 2 items in your values array, and, assuming you do, you initialize your three variables:

boolean increasing = values[0] < values[1];
int sum = values[0];
int len = 1;

int maxlen = len;
int maxsum = sum;

OK, we set up the system where we expect the third value to be a continuation of the sequence.... and then we start the loop, starting from position 1 (the second item) in the values array:

for (int i = 1; i <= arrays.length; i++) {
    // check here to see if we are going in the same direction
    if ( (increasing && value[i] >= value[i -1]) || ( ...decreasing and next is smaller) ) {
        // we are going on in the same direction as before:
        // increase the length, and add value[i] to the sum.
        // if the length is larger than maxlen, then change maxlen and maxsum to len and sum
    } else {
        // the value at position i breaks the sequence.
        // reset len and sum to be 2 and the sum of this and the previous value

        // EDIT: 'Obviously' you record the change in direction!
        increasing = !increasing;

    }
}

System.out.printf("The longest sequence is %d values long, and has a sum of %d\n", maxlen, maxsum);

Without going in to too much detail, you can easily convert this algorithm to work at the same time as you process the user input.... there is no real reason why you have to first convert all the values to int first, and only then process them.... you can process them as they are entered.

EDIT: I realize you may need to be smarter than I have suggested when setting up the variables initially... if the first values in the input are all the same then the algorithm above will assume the sequence is not increasing and will produce the wrong result. You need to find out the initial 'direction' of the sequence by looking for the first 'different' value

\$\endgroup\$
  • \$\begingroup\$ Thank you for ur answer. Problems will appear where sequence have more than 1 the same variables. For example, for "0 0 1 1 2 2" exit will be "length - 6, summ - 6", early i made exactly like you said. When 2 numbers like " 0 0 " appear, i need to keep INCREASE and DECREASE flags on.... \$\endgroup\$ – Alex Nov 15 '13 at 12:03
  • \$\begingroup\$ Apart from the very first numbers (which I have already mentioned), your concern about duplicates is not valid. Using >= for increasing and <= for !increasing will keep it right \$\endgroup\$ – rolfl Nov 15 '13 at 12:28
  • \$\begingroup\$ You are right, but when in will be " 0 0 1 1 2 2 3 3 3 2 1 1 1 0 0 0" by ur program logic out will be " 0 0 1 1 2 2 3 3 3". A correct answer must be " 3 3 3 2 1 1 1 0 0 0" this sequence length is bigger on 1. \$\endgroup\$ – Alex Nov 15 '13 at 12:47
  • \$\begingroup\$ it's appear because in the same time we have parts of decreasing and increasing sequences \$\endgroup\$ – Alex Nov 15 '13 at 13:02
  • \$\begingroup\$ Perhaps there was something so 'obvious' I neglected to put it in to the comments... let me edit my answer.... \$\endgroup\$ – rolfl Nov 15 '13 at 13:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.