How to find a sequence with max sum in an array

[adityakiran]

Hi all, I have another query. I am trying to wite a piece of asm code using 32 bit registers (eax, ebx etc.,) to get a subsequence of lenght say L in an array a whose sum is maximum, some thing like the folowing c++ code

int GetMaxSubSeq(int* a, int sublen, int* start, int* end)
{
   int sum=-2001, temp;
   for(int i=0;i<LEN-sublen;i++)
   {
      temp=Sum(a, i, i+sublen-1);
      if(sum<temp)
      {
         sum=temp;
         *start=i;*end=i+sublen-1;
      }
   }
   return sum;
}

The func when passed with array a, its start and end and sublenth l will return the max sum of a sub sequence of lenth l in the array a. I tried to convert the same login into an asm program but could not...can some one jus show me a sample of how i can write the abov elogic in asm? Plez suggest..!

Thanks, Aditya

[Mirno]

If you are trying to get a speedup, the first thing to do is design a faster algorithm.
Your repeated calls of Sum are wasteful (I'm guessing they add all the numbers from a[X..Y] and return that value), you know most of the total anyway, so it's a waste to throw it away...

Code Select Expand


int GetMaxSubSeq(int* a, int sublen, int* start, int* end)
{
  int sum, temp;
  int i;

  temp = sum = Sum(a, 0, sublen - 1);

  start = 0;

  for (i = 1; i < (LEN - sublen); i++)
  {
    temp -= a[i];
    temp += a[i + sublen - 1];

    if (temp >= sum)
      *start = i;
  }

  *end = *start + sublen - 1;

  return sum;
}

Should be much faster C code.

Seeing as you've tried, can you post that code and we'll have a look at it to tell you where you've gone wrong.
It's an odd bit of code to start with, I'd suggest you start with more simple tutorials and build up from there rather than go diving in to single function.

Mirno

[adityakiran]

Thanks for the instant response, as u said its an odd bit of code to start with. But its a part of a problem i am trying to solve. actually the problem is to find a subsequence whose sum is max and another subsequnce whose sum is min given the array and lengh of the subsequnce. It is also required to initiallize the array with random numbers between
-2000 and 2000.
I could initialize the array with random numbers calling a c file that generates numbers using the rand func

#include<stdio.h>
#include<time.h>
#include<stdlib.h>
int _asm_main( void );

int _randnum()
{
   return 2000-(rand()%4000+(time(NULL))%4000)%4000;

}

int main()
{
  int ret_status;
  ret_status = _asm_main();
  return ret_status;
}
I called this func in my asm prog like this    
                mov ebx,ecx
   call _randnum
   mov [esi],eax
   mov ecx,ebx
   add esi,4
   loop fun


   mov ecx,100
   mov esi , input1

i got the array now. I am actually not able to write the assemble code to the function i pasted in my previous post, unfortunatly i missed the class at college on this asm programs bcz of heavy work at office. Particularly i am not able to know from which register to which register movements are required. As far as the efficiency is concerned i dint spend time to think about the logic, i jus wrote it thinking if i can convert this into asm i can think of a better logic.
Though i read the rule of the forum that homework's should not be posted, i could not help requesting for help :(. I am very new to asm and unfortunatly missed my class also. If u think u can help me plez, else i shell have to read more into it and complete it.

Thanks, Adityakiran