Largest Element in the Stack

Problem: Given a stack you have to insert a stream of numbers in it and you have to keep track of the highest element at any point in the stack

In general, the solution will require traversing through the entire stack hence taking O(n) time. However, given the option of using another data-structure this can be done using minimal extra memory using another "Stack" !.

The basic idea is when pushing an element in the original, check if the the "highest_elem_stack" is empty or if its top element is less than or equal to the element being pushed, if yes push this element on both stacks.

While popping check if the popped element is equal to the top element of the "highest_elem_stack". If yes pop both stacks.

The highest element in the original stack would always be equal to the top element in the "highest_elem_stack"

Maximum Sum Sub array

This is a interesting problem which can be solved in a variety of ways. This problem has a chunk of a chapter devoted in the Programming Pearls book by Jon Bentley.

Method 1. Brute Force O(n^2)

This involves taking each index i between 0 to len and for every other index j>i calculate the sum while keeping track of the maximum.

private static int sumbruteforce(int [] arr){
  int sum=0;
  int max=Integer.MIN_VALUE;
  int maxi=0;
  int maxj=0;
  for(int i=0;i<arr.length;i++){
   sum=0;
   for(int j=i;j<arr.length;j++){
    sum+=arr[j];
    if(sum>max){
     max=sum;
     maxi=i;
     maxj=j;
    }
   }  
  }
  System.out.println(maxi+" "+maxj);
  return max;
 }

2. Method 2: Divide and Conquer: O(n log n)
This involves dividing the array recursively into 3 parts left, right and mid. And comparing max sum of the three.

Calculating max(left) and max(right) is trivial using recursion. For the mid element, we know the left bound (l) lies in left half and right bound (r) lies in right half. So we calculate l s.t sum of elements between l and mid is max and r s.t the sum is maximum for elements between mid and right.

private static int sumDivConquer(int [] arr, int l, int h){
  if(l>h)
   return 0;
  if(l==h)
   return arr[l];

  
  int m=(int) Math.floor((double)((l+h)/2));
  int max=0;
  
  max=sumDivConquer(arr, l, m);
  max=Math.max(max,sumDivConquer(arr, m+1, h));
  
  
  int L=0;
  int R=0;
  int S=0;
  for(int i=m;i>=l;i--){
   S+=arr[i];
   L=S>L? S:L;
  }
  R=S=0;
  for(int i=m+1;i<=h;i++){
   S+=arr[i];
   R=S>R? S:R;
  }
  max=Math.max(max, L+R);
  
  return max;     
 }

3. Dynamic programming O(n)

An optimized DP solution takes O(n).

The naive DP solution acts exactly like method 1 and generates a matrix A[i,j] containing sum of elements with left bound i and right bound j.

The optimized DP constructs a single dimension table of array size, with
table[i]: Represents the sum of subarray with maximum sum terminating at i;

for i=0, table[0]=arr[0]
for i>0, table[i]= Max{ arr[i], arr[i]+table[i-1]}

Once we have the table finding max sum takes only a single pass through the above table, we can fasten the procedure up by keeping track of max side by side.

private static int sumDP(int [] arr){
 int table[]=new int[arr.length];
 table[0]=arr[0];
 for(int i=1;i<arr.length;i++){
  table[i]=Math.max(arr[i], arr[i]+table[i-1]);
 }
 int max=Integer.MIN_VALUE;
 for(int i=0;i<arr.length;i++){
  if(table[i]>max)
   max=table[i];
 }
 return max;
}
 

A simpler algorithm based on the same idea as the DP method is called Kadane's algorithm and it works without the need of maintaining the auxiliary table.

The code is derived from here

private static int sumKadane(int arr[]){
    int max=Integer.MIN_VALUE;
    int a,b; a=b=0;
    int curr = 0;
    int aa = 1;
    for (int bb= 1;bb<arr.length;bb++){
        curr = curr + arr[bb];
        if (curr > max) {
            max=curr;
            a=aa;
            b=bb;             
        }
        
        if (curr < 0) {
            curr = 0;
            aa = bb + 1;
        }
    }
    System.out.println(a+" "+b);
    return max;
}

Memoization

From wikipedia:
Memoization is an optimization technique used primarily to speed up computer programs by having function calls avoid repeating the calculation of results for previously-processed inputs. Memoization is also used in Dynamic Programming.

Memoization typically requires maintaining a look up table where calculated values of previous function calls are kept.

Naive examples where memoizaton can help is:
1. Factorial
2. Fibonacci Series

I will take up a small problem to show the technique:
Lets say we have to calculate value of a function A which is defined by:
An = A[n/p] + A[n/q] for all n >= 1, where [x] denotes the floor function of x.

for a given value of n.

A naive implementation looks like this:

using System;
using System.Collections.Generic;
using System.Text;
using System.Diagnostics;

namespace TC1 {
    class Program {
        Dictionary  mem =new Dictionary() ;
        long calc1 (long n, int p, int q) {
            if (n == 0)
                 return 1;
             long np = (long) Math.Floor((double)n / p);
             long nq = (long) Math.Floor((double) n / q);
             return calc1(np ,p , q) + calc1(nq, p ,q);
        }
        long calc2 (long n, int p, int q) {
            if (n == 0)
                return 1;
            long val;
            if (mem.TryGetValue(n, out val)) {

            } else {
                long np = (long) Math.Floor((double) n / p);
                long nq = (long) Math.Floor((double) n / q);
                val = calc2(np, p, q) + calc2(nq, p, q);
                mem.Add(n, val);
            }
            return val;
        }      

        static void Main(string [] args) {
            Program p = new Program();
            Stopwatch w = new Stopwatch();
            w.Start();
            Console.WriteLine(p.calc1(10000000, 2, 3));
            w.Stop();
            Console.WriteLine(w.Elapsed);
            w.Reset();
            w.Start();
            Console.WriteLine(p.calc2(10000000, 2, 3));
            w.Stop();
            Console.WriteLine(w.Elapsed);
        }
    }
}

First of all, this is not the best way to benchmark techniques, but it does give a good general indication. As the value of n increases the memoization techniques is faster by more that a factor of 10 in many cases.

However, in some cases you have to tread carefully when there is a space constraint too. In most cases, the problem can be solved by using a threshold above which no memoization is done.