LintCode "Continuous Subarray Sum"

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;
}
};
上一篇:Continuous Subarray Sum II


下一篇:jquery插件:仿百度首页可展开收起的消息提示控件