Max subarray sum problem

#1

How will I know that, this problem is a do problem?

#2

@Sagarjha07 Your question is not clear. what do mean?

#3

How will I know that this is a *DP problem?

#4

For DP, there must be 2 conditions that should be followed by our problem:-

  1. Overlapping subproblems :- It means while finding solution, if our problem is getting divided into subproblems, which are repeated again and again.
    So according to this question, while calculating sum from i to j there will be many subarray between i and j which have been calculated again and again. It can be optimized by applying DP.
  2. Optimal Substructure :- It means when the required answer is actually depending upon the optimal answer of subproblems and actually is some combination of them.
    Here lets say i, j, k are index of array such that i<j<k, so the answer for i to k will depend upon the optimal answer i.e. max sum of i to j.
    Hope you have got some idea, how to detect DP problem from this.