// Three bad implementations. // Author: Ali Taleghani // // Consider the following three functions foo, bar and baz. // They present three different implemenations of the same // functionality. Rank them in the following categories. // Explanation follows. // // READABILITY: You haven't seen these functions before, and // don't know what they are to do. Rank the most // readable as 1 and least readable as 3. // // TIME COMPLEXITY: Rank the algorithm that takes the least // amount of time as 1; the most time consuming as 3. // // SPACE COMPLEXITY: Rank the function that takes least space as // 1 and that with most space used at 3. // // Readability | Time Complexity | Space Complexity // 1. // // 2. // // 3. // // #include #include using namespace std; void foo () { int p, cs, ce, c; int m = -1, ms, me; cs = ce = 0; c = 0; for (int i = 0; i < 6; i++) { cin >> p; if (p >= 0) { ce++; c += p; } else { if (c > m) { m = c; ms = cs; me = ce; } cs = ce = i + 1; c = 0; } } if (c > m) { m = c; ms = cs; me = ce; cs = ce = 0; c = 0; } cout << "The best part of the route is between " << ms << " and " << me << endl; } // Reads a sequence from std-in, prints the start and // end of the positive subsequence with largest sum. void bar () { const int NUMBER_COUNT = 6; vector sequence(NUMBER_COUNT); // Read the sequence into a vector for (int i = 0; i < NUMBER_COUNT; i++) { int thisNumber; cin >> thisNumber; sequence[i] = thisNumber; } // These keep track of the best sub sequence we have found // so far. int bestSubStart = 0, bestSubEnd = 0; int bestSubSum = -1; for (int start = 0; start < NUMBER_COUNT; start++) { for (int end = start; end < NUMBER_COUNT; end++) { int sum = 0, j; bool hasNegatives = false; for (j = start; j <= end; j++) hasNegatives = hasNegatives || (sequence[j] < 0); if (hasNegatives) continue; for (j = start; j <= end; j++) sum += sequence[j]; cout << start << ":" << end << " => " << sum << endl; if (sum > bestSubSum) { bestSubStart = start; bestSubEnd = end; bestSubSum = sum; } } } cout << "The best part of the route is between " << bestSubStart << " and " << bestSubEnd + 1 << endl; } // Reads a sequence of 6 numbers from standard input, prints the start // and end of the positive subsequence with largest sum. // We only need to look at subsequences surrounded by negative // numbers. This can be done online. O(n) time, O(1) space. // NOTE: subsequences of length 1 are allowed // NOTE: the printed END should always be one passed the // real end, of the subsequence. // e.g. for 1 -1 12 3 -1 78 we should get start=5, end=6 void baz () { // Maintain a best subsequence (start, end, sum) // sum > 0 is true of any acceptable subseqence // Also maintain a current subsequence (start, end, sum) int bestStart = 0, bestEnd = 0, bestSum = -1; int currStart = 0, currEnd = 0, currSum = 0; int thisNumber; for (int i = 0; i < 6; i++) { cin >> thisNumber; if (thisNumber >= 0) // add it to the current { currEnd++; currSum += thisNumber; continue; } // negative; compare with best and switch start, end, sum. if (currSum > bestSum) { bestSum = currSum; bestStart = currStart; bestEnd = currEnd; } currSum = 0; currStart = currEnd = i + 1; } // need this one more time, to check for the // subsequence that ends with end of our sequence // e.g. 1 -1 2 3 4 if (currSum > bestSum) { bestSum = currSum; bestStart = currStart; bestEnd = currEnd; } cout << "The best part of the route is between " << bestStart << " and " << bestEnd << endl; } int main() { int n; baz(); cin >> n; return 0; }