CareerCup

Using Deque can solve this problem in O(N) time

deque is a queue that can be pushed/popped from both ends. We use a deque DQ to store the elements for the sliding K-window. The trick is that, we only store the elements that are potentially be the maximum of future K-windows. So, if we see a number x that is greater than all elements in the current deque, we know for sure that x now will be the max, and all those elements in current deque will never be the max again. Thus, they must be removed, replacing by x.

Example:
A = [8, 5, 10, 7,9, 4, 1, 1, 1…]
We see 8: nothing to compare
When we see 5: we know that when 8 is out of the future K-window, 5 can potentially be the max of that window. We need to store 5

When we see 10: we know that 8, 5 can never be the max for future K-window. Thus, 8,5 should be removed. The deque now contains only 10

When we see 7: 7 can potentially be the max when 10 is out. Store 7, deque becomes [10, 7]

When we see 9: 7 won’t be the max anymore, remove 7. Store 9, deque becomes [10,9]

And so on..

EDITED: I explained it here:
capacode. com/?p=1042

There is a recurrent formula - dp[i] = Math.max(nums[i+k-1], dp[i-1]), where dp contains all our problem states (dp[i] is the max element in subarray with length k that start at index i).

{
  void findMaxKSubArray(int[] nums, int k) {
	  if (nums.length < k) {
		  throw new IllegalArgumentException();
	  }
	  int dp[] = new int[nums.length - k + 1];
	  int max = Integer.MIN_VALUE;
	  for (int i = 0; i < k; i++) {
		  max = Math.max(max, nums[i]);
	  }
	  dp[0] = max;
	  for (int i = 1; i <= nums.length - k; i++) {
		  dp[i] = Math.max(nums[i+k-1], dp[i-1]);
	  }
	  for (int i = 0; i <= nums.length - k; i++) {
		  System.out.print(dp[i]+ " ");
	  }  
  }

I dont see this specific as a DP problem until and explicitly told to solve it in DP..

DP Algo As follows.

void Solution(int []array)
{
for(int i = 0; i < (array.length - k) l i++)
{
print 'findMax(i , i +k , array)';
}

}

int findMax(int start, int end, int []array)
{
// use careful data structure like priority queue to get the max in O(1) time.
}

O(n) solution without deque.
c# implementation.
Edited after ninhnnsoc's comment.

private static int[] Get1( int[] arr, int k ) {

    int t = 0;
    int[] res = new int [ arr.Length - k + 1 ];
    List<int> list  = new List<int> { 0 };

    for ( int i = 1; i < arr.Length; i++ ) {
                                
        if ( list.Count == 0 || arr[ i ] > arr[ list[ t ] ] ) {
            list = new List<int> { i };
            t = 0;
        }
        else                
        if ( arr[ i ] < arr[ list[ t ] ] ) {
            var target = arr[ list[ list.Count - 1 ] ];
            if ( arr[ i ] > target ) {
                list = new List<int> { list[ 0 ] };                        
            }
            list.Add( i );
        }

        if ( i >= k - 1 ) {
            res[ i - k + 1 ] = arr[ list[ t ] ];
            if ( arr[ i - k + 1 ] == arr[ list[ t ] ] ) {
                t++;
            }
        }
    }
    return res;
}

Without dynamic programming just using a couple of nested loops you end up with something that is O(nk) in complexity
You could use this relationship to do dynamic programming
F(i,k) = max (F(i,k-1), A[i+k])
Where i is an index and A is the array
But this is not very satisfying since you are still at O(nk)
Using this relation
F(i,k) = max(F(i, floor(k/2)), F(i, ceiling (k/2)))
This gets you down to O(n*log(k))
memoization would be good at this point an make for a simple implementation.
But let's see if we can do it bottom up.
Write a recursive program to compute the values of k we need. If we compute all maxes for k we will compute a lot of values we don’t need.
We will need to store these values of k into some fancy data structure which denotes the order of computation for the different table lengths if hearts the brain just to think about it.
For the value k = 51 you need k = 25 and k = 26
For k = 25 you need 12 and 13
For 26 you need 13
For 12 you need 6
For 13 you need 7 and 6
For 7 you need 4 and 3
For 4 you need 2
For 3 you need 2 as well
You can compute 2 then 3 and 4 then 6 and 7 then 12 and 13 then 25 and 26 then 51
It is a pain
So try a different approach
Store the first k items in a balanced binary search tree that has O(log(k)) complexity
Store the biggest one that is the max of the first k elements in your table as element 0
Now remove the first one from the tree. It will take O(log(k)) to do this
Now add the next element A[k+1]
that will take another O(log(k))
Store the biggest one that is the max of the next k elements.
Yet another O(log(k))
I don’t think this counts as dynamic programming but it is O(n*log(k)) time complexity
And you only need enough extra memory to store the tree for k elements.

Nums = 7,3,1
for (int i = 0; i < k; i++) {
max = Math.max(max, nums[i]);
}
Max (7, 3)
dp[0] <-7
dp[1] = max( nums[2] , dp[0])
dp[1] = max(1, 7 )
dp[1] <- 7
it should be
max (3,1)
3
Or at least that is how a parse the question

void maxOfEachSubArrayofSizeK(int iArr[N],int k)
{
	int max=0,j=0,iCnt=0;
	int iMaxValue[n];
	max = iArr[0];
	for(int i=0;i<N;i++)
	{
		if(iCnt ==k)
		{
			iMaxValue[j] = max;
			iCnt = 0;
			max=0;
			j++;
		}
		if(max < iArr[i])
			max = iArr[i];
		iCnt++;
	}
	iMaxValue[j] = max;
}

the task is a bit unclear.
Could the author please specify via example the needed output?
Say, given array {9,8,7,6,5,4,3,2,1,0} and k = 4.
What should be the output?

c# implementation.

using System;

namespace MaxContiguousArrays{

    class Program {

        private static int[] Get( int[] arr, int k ) {

            int[] dp = new int [ arr.Length - k + 1 ];
            dp[ 0 ] = Math.Max( arr[ k - 1 ], GetMaxInSubArray( arr, 0, k - 1 ) );

            for ( int i = 1; i < arr.Length; i++ ) {
                var iAhead = i + k - 1;
                if ( iAhead >= arr.Length ) { break; }
                dp[ i ] = arr[ iAhead ] > dp[ i - 1 ]
                          ? arr[ iAhead ]
                          : Math.Max( arr[ iAhead ], GetMaxInSubArray( arr, i, k - 1 ) );
            }
            return dp;
        }

        private static int GetMaxInSubArray( int[] arr, int start, int k ) {

            int maxVal = arr[ start ];
            for ( int i = start; i < start + k; i++ ) {
                if ( arr[ i ] > maxVal ) {
                    maxVal = arr[ i ];
                }
            }
            return maxVal;
        }

        static void Main(string[] args)
        {
            var res = Get(new int[] { 9,8,7,6,5,4,3,2,1,0 }, 4);
        }
    }
}

It is the same question as "find out maximum in the window of size K in an array." To answer this you have to use the priority queue and such. Basically here what we have to do is this:
Use the queue for this and its size should be equal "K".
1. Put the first element in the queue.
2. Put the second element in the queue but before doing that compare its value to the top of the queue and see if its value is greater. If it is, then remove the top of the queue until the top of the queue is no longer more that the element which you are going to insert or there is no longer any element in the queue.
3. Do the same for all the successive elements.
4.After you have inserted K elements remove from the bottom of the queue and that will be the largest element in the queue. Do this for every window of size K i.e. after you have found the biggest element in the window size of K initially, you should do the same whenever you are inserting a new element. Why? Because the new element addition will be the new window of size K.

Here is a method that is guaranteed to get O(n(logk)) which is attractive is k is large and close to n. In this method, we use a Dictionary<int,int> to store the counts of numbers in the K window and a SortedSet<int> (available in .Net) storing the sorted different elements seen in the window. The sortedSet implements a red-black tree, allowing sorted inserts and remove of log n (n => k in this case).

For each movement of the window, we remove the last element of the window from the Dictionary, if this deletes the count of that element goes to 0, we remove it from the sortedSet as well, in O(logk) time. Then we Add an element into the dictionary, if it exists, we increment the count, if it doesn't we insert it in the dictionary, and Add it to the sortedSet, again in O(logk) time.

I implemented a class KWindow that contains my SortedSet and my dictionary to abstract Adding and Removing.

public static void PrintMax(int[] A, int k)
        {
            KWindow kWindow = new KWindow();
            // fill first window and print
            for (int i = 0; i < Math.Min(k,A.Length); i++)
            {
                kWindow.Add(A[i]);
                Console.WriteLine(kWindow.listInts.Max);
            }

            for (int i = 1; i <=A.Length- k; i++)
            {
                kWindow.Add(A[i+k-1]);
                kWindow.Remove(A[i - 1]);
                Console.WriteLine(kWindow.listInts.Max);
            }
        }

        public class KWindow
        {
            public SortedSet<int> listInts;
            public Dictionary<int, int> numCounts;

            public KWindow()
            {
                listInts = new SortedSet<int>();
                numCounts = new Dictionary<int, int>();
            }

            public void Add(int value)
            {
                if (numCounts.ContainsKey(value))
                {
                    numCounts[value]++;
                }
                else
                {
                    numCounts.Add(value, 1);
                    listInts.Add(value);
                }
            }

            public void Remove(int value)
            {
                if (numCounts.ContainsKey(value))
                {// don't really need to check in this application but to be reusable
                    if (numCounts[value] == 1)
                    {
                        numCounts.Remove(value);
                        listInts.Remove(value);
                    }
                    else
                    {
                        numCounts[value]--;
                    }
                }
            }
        }

Running this on

int [] Arr = new int[] {1,2,2,4,5,45,6,7,4,3,4,5,6,3,9};
            PrintMax(Arr,4);

gives
1,2,2,4,5,45,45,45,45,7,7,5,6,6,9

it is a O(n) algorithm.

maxv = sum(A[1] to A[k])
for i = k+1 to n:
tp = maxv - A[i-k] + A[i]
if tp > maxv:
maxv = tp

print maxv