# Solution to the stock span problem

a guest
Oct 4th, 2012
337
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
1. package com.test.project.stockSpan;
2.
3. import java.util.Stack;
4.
5. /*Span of a stock on a given day, is the maximum number of consecutive days just before the given day, for which the price of the stock is less than or equal to the price of stock on the given day.
6. Let Price(i) = price of the stock on day "i".
7. Span(i) = max{k : k<=i and Price(j)<=Price(i) for j=i-k, .., i}
8. Thus, if Price(i-1)>Price(i), then Span(i)=0.*/
9.
10. public class StockSpan {
11.
12.     public static int[] spanOfStocks(int[] price, int n, boolean useStacks) {
13.         if(!(useStacks))
14.         {
15.             //Calculate span in O(n^2) time without using stacks
16.             int[] span1 = new int[n];
17.             for(int i=0;i<=n-1;i++)
18.             {
19.                 int k=0;
20.                 boolean done = false;
21.                 while((!done)&&(k<=i))
22.                 {
23.                     if(price[i-k]<=price[i])
24.                     {   k++;}
25.                     else
26.                     {   done = true;}
27.                 }
28.                 span1[i] = k;
29.             }
30.             return span1;
31.         }
32.         //Calculate span in O(n) time using stacks
33.         int[] span2 = new int[n];
34.         Stack<Integer> stack = new Stack<Integer>();
35.         for(int i=0;i<=n-1;i++)
36.         {
37.             int k=0;
38.             boolean done = false;
39.             while((!(stack.isEmpty())) && (!done))
40.             {
41.                 if(price[i]>=price[stack.peek()])
42.                 {stack.pop();}
43.                 else
44.                 {done = true;}
45.             }
46.             int h = 0;
47.             if(stack.isEmpty())
48.             {h=-1;}
49.             else
50.             {h=stack.peek();}
51.             span2[i]=h-i;
52.             stack.push(i);
53.         }
54.         return span2;
55.     }
56. }