How is Kadane's Algorithm DP?

general
1

I’ve been studying a lot of DP lately, and I’ve recently cleared up the confusion between Memoization(top-down DP or recursive DP) and iterative DP(bottom up DP).

The LIS problem does satisfy the necessary requirements for a problem to be solved by DP… Optimal substructure and overlapping subproblems. But the problem is I don’t see any already-solved subproblem solutions being stored and reused.

When Kadane’s Algorithm is under DP everywhere, I’m sure it shouldn’t be wrong.

So the real problem is what part of DP have wrongly understood, that’s making me think that this algorithm is not DP.

How can you tell if an iterative algorithm is a bottom-up DP? How do you guys know this by looking at an algorithm?

2

Kadane’s Algorithm finds the greatest sum subarray ending at some index i and for every index in the array. Now, it follows the recurrence relation- dp[i] = max(dp[i-1] + ar[i], ar[i]);

I can clearly see repeated computations being used, dp[i-1], so to speak.

4 Likes
3

I’m talking about the iterative version:

int n,till_here=0, so_far=0;
            cin>>n;
            int arr[n];
            for(int i=0;i<n;i++)
                    cin>>arr[i];
            for(int el:arr){
                    till_here+=el;
                    if(till_here<0)
                            till_here=0;
                    if(so_far<till_here)
                            so_far=till_here;
            }
            cout<<so_far<<endl;

??

4

dp[i] = max(dp[i-1]+a[i],a[i])
this is the recurrence formula for kadane’s algorithm. If you observe the formula, you would see that you don’t need an array since you only need “i-1” i.e last state. So instead of storing all the states in an array, just use another variable called ‘till_here’. But you also need to store the global maximum, so use another variable called so_far.
So now, it becomes,
till_here = max(till_here+a[i],a[i]) so_far = max(so_far,till_here)
So it is still dp but you don’t need to store all states because you only need the last state.
Hope this is clear now

5 Likes
5

Slightly more clear now :slight_smile:

1 Like
6

The one I talked about is still iterative, it is not recursive. The case here is much like finding the nth Fibonacci number. In Fibonacci number, we only need the previous two states to calculate the current state, but if don’t store the answer of those states, it would lead into chain of repeated computations, because those two previous states would further need the result of their previous two states and so on.
The situation is not very different here, we need only the last previous state but if don’t store it will lead to a chain of repeated computations.

2 Likes
7

Yep, got it!
(filler to make post at least 20 chars long)

8

You can try Kadane’s algorithm in this : Calvin’s game