Databases
StackOverflow2013
Postsdbo
POCalculate Profits faster than O(n!)
 

Note that there are some explanatory texts on larger screens.

plurals
  1. POCalculate Profits faster than O(n!)
    primarykey
    data
    text
    <p>So last week I posted a problem for the ACM ICPC South East Regionals here -> <a href="https://stackoverflow.com/questions/4158264/algorithm-to-calculate-the-number-of-1s-for-a-range-of-numbers-in-binary">Algorithm to calculate the number of 1s for a range of numbers in binary</a>. It was pretty well recieved and still hasn't been solved so I figured why not throw up another question my team couldn't solve.</p> <p>The Problem.</p> <blockquote> <p>Your friends have just opened a new business, and you want to see how well tehy are doing. The business has been running for a number of days, and your friends have recorded their net profit on each day. You want to find the largest total profit that your friends have made during any consecutive time span of at least one day. For example, if your friends profits looked like this:</p> </blockquote> <pre><code>Day 1: -3 Day 2: 4 Day 3: 9 Day 4: -2 Day 5: -5 Day 6: 8 </code></pre> <blockquote> <p>Their maximum profit over any span would be 14, from day 2 to 6.</p> <p><strong>Input</strong><br> There will be several test cases in the input. Each test case will begin with an integer N ( 1 &lt;= N &lt;= 250,000) on its own line, indicating the number of days. On each of the next N lines will be a single integer P (-100 &lt;= P &lt;= 100), indicating the profit for that day. The days are specified in order. The input will end with a line with a single 0</p> <p><strong>Output</strong><br> For each test case, output a single integer, representing the maximum profit over any non-empty span of time. Print each integer on its own line with no spaces. Do not print any plank lines between answers.</p> </blockquote> <p><strong>Sample Input</strong></p> <pre><code>6 -3 4 9 -2 -5 8 2 -100 -19 0 </code></pre> <p><strong>Sample Output</strong></p> <pre><code>14 -19 </code></pre> <hr> <p>The code to solve this problem is pretty simple if you do not worry about efficiency but the only way it was solved at the contest was at O(n!), which is un-acceptable. I hope stack overflow can do better</p> <p>Good luck!</p> <p><strong>EDIT</strong></p> <hr> <p>Just to keep this updated here is completed code that solves this problem in O(n).</p> <pre><code>import java.util.Scanner; public class Profits { public static int seqStart=0, seqEnd=-1; public static void main(String args[]) { Scanner s = new Scanner(System.in); while (s.hasNextLine()) { int current = s.nextInt(); if (current == 0) break; else { int count = current; int[] a = new int[count]; for (int x = 0; x &lt; count; x++) { a[x] = s.nextInt(); } System.out.println(max_subarray(a)); } } } private static int max_subarray(int[] a) { int maxSum = a[0], thisSum = a[0]; for(int i=0, j=0;j&lt;a.length;j++) { thisSum = thisSum + a[j]; if(thisSum &gt; maxSum) { maxSum = thisSum; seqStart = i; seqEnd = j; } else if (thisSum &lt; 0) { i = j+1; thisSum = 0; } } return maxSum; } } </code></pre>
    singulars
    1. PO
      singulars
      1. PTAnswer
    1. This table or related slice is empty.
    1. PTQuestion
    1. USCommunity
    1. USaustinbv
    plurals
    1. PL
      singulars
      1. LTLinked
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. PO
      singulars
      1. PTAnswer
    1. VO
      singulars
      1. POCalculate Profits faster than O(n!)
      1. This table or related slice is empty.
      1. VTUpMod
    2. VO
      singulars
      1. POCalculate Profits faster than O(n!)
      1. This table or related slice is empty.
      1. VTUpMod
    1. COI think that the brute force method of trying all solutions should be `O(n^2)`, not `O(n!)`. For `n` days, there are exactly `n(n+1)/2` possible contiguous non-empty spans of time.
      singulars
      1. POCalculate Profits faster than O(n!)
      1. USSteve Tjoa
 

Querying!

 
Guidance
A row detail

Detail views are divided into sections. All the information in the data section comes from columns in the selected row. The other sections display data from other, related rows.

Related data can be related in a to-one or a to-many fashion. Captions of data related in a to-many fashion link to a list view showing a filtered view of the table.

Try moving around until you find a non-empty to-many entry and click on the label to get to one. You can move back to the root by clicking on the database name in the header.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload