A variation to a classical DP: LCS.
class Solution {
public:
/**
* @param A an integer array
* @return A list of integers includes the index of
* the first number and the index of the last number
*/
vector<int> continuousSubarraySum(vector<int>& A) {
vector<int> ret;
size_t len = A.size();
int curr = A[];
int sum = A[], csum = A[];
int s = , e = , ss = , ee = ;
for (int i = ; i < len; i++)
{
int nsum = csum + A[i];
if (A[i] > nsum)
{
ss = ee = i;
csum = A[i];
}
else
{
ee = i;
csum = nsum;
}
if(csum > sum) // update global record
{
sum = nsum;
s = ss;
e = ee;
}
}
ret.push_back(s);
ret.push_back(e);
return ret;
}
};