s*******f
发帖数: 1114 | 1 //1.Given an array, find the longest subarray which the sum of the subarray
//less or equal then the given MaxSum
//int[] FindMaxSumArray(int[] array, int maxsum)
//can only deal with all positive, or all negative
void FindMaxSumArray(int *in, int len, int *out, int maxsum){
if (!in || len < 1 || !out)
return 0;
int i = 0;
int j = 0;
int sum = 0;
int maxi = 0;
int maxj = 0;
while(j < len){
sum += in[j];
if (sum > maxsum){
if (j - i ... 阅读全帖 |
|
l*******0
发帖数: 95 | 2
这是一个典型的动态规划问题。
distance = A[i] -i + A[j] + j. 需要用动态规划来保存后面的A[j] + j的最大值状
态。
int solution(int[] A) {
if(A == null || A.length == 0) return 0;
// state[i] is the offset j satisfying that A[j] + j >= A[k] + k for any
k >= i
int[] state = new int[A.length];
// initial distance
state[A.length - 1] = A.length - 1;
// state update function
for(int i = A.length - 2; i >= 0; i --) {
int current = A[i] + i;
int maxJ = state[i+1];
if(current >= maxJ ... 阅读全帖 |
|
h**6
发帖数: 4160 | 3 用力矩的算法，复杂度O(n^2)
#include
#include
#include
#include
using std::string;
using std::vector;
using stdext::hash_map;
void weightcenter(string str)
{
int n = str.size();
vector w(n);
for(int i = 0; i < n; i++) {
w[i] = str[i] - '0';
}
vector >weight(n, vector(n));
vector >torque(n, vector(n));
int maxlen=-1, maxi=-1, maxj=-1;
for(int len = 1; len <= n/2; len++) {
hash_map阅读全帖 |
|
i******r
发帖数: 323 | 4 来自主题: Programming版 - 问个算法题 动态规划
假设N > 0
double max, curr=-1;
int maxI = -1, maxJ; //use maxI == -1 to denote that max = -infinity
int currI;
for (int i = 0; i < N; ++i) {
if (curr < 0) {
curr = 0;
currI = i;
}
curr = curr + a[i];
if (maxI < 0 || curr > max) {
maxI = currI;
maxJ = i;
max = curr;
}
}
//now maxI and maxJ is what you want
//complexity O(N) |
|
