Largest sum subarray

Recursion: M[i] = max sum subarray ending here

M[i] = max(M[i-1] + a[i], a[i])

Loved this code 🙂

#include<algorithm>
#include<iostream>

using namespace std;

int main() {
  int n;
  cin >> n;
  int max_sum = 0, run_sum = 0;
  for (int i = 0, t = -1; i < n; ++i) {
    cin >> t;
    run_sum = max(run_sum + t, t);
    max_sum = max(run_sum, max_sum);
  }
  cout << max_sum << endl;
  return 0;
}
Advertisements

About Avi Dullu
Jaako rakhe saiyan, maar sake na koi!

6 Responses to Largest sum subarray

  1. Venki says:

    Recursion is always a powerful weapon in algorist’s arsenal. It may not lead to best complexity, but worth exploring.

    Isn’t the above code is Kadane’s algorithm? I am not clear, why t being initialized to -1, as it will be overwritten immediately.

    It is even more interesting to solve the problem without difference array (CLRS 3e, explicitly solved stock profit maximize problem), and whether, can we come up with online algorithm as the one in the post?

    On similar lines, finding a *subsequence* of length K whose sum is maximum over all those possible subsequences of length K. Recursion plays critical role (I found it is quite helpful to draw the tree diagrams).

  2. Avi Dullu says:

    Not really sure about the Kadane’s algorithm. I was just “compressing” the code and was able to bring it down to this 🙂
    About t = -1, I prefer making it a habit to initialize a variable always.
    The subsequence problem sounds a good one. Will sleep over it. Thanks 🙂

  3. Venki says:

    Aah, I am forgetting the old golden rule. While developing SW for aircrafts, we were mandated to initialize every local variable as defensive programming.

    If the compiler is intelligent enough, it can remove the first assignment, where there is no use of the identifier in-between two consecutive assignments.

    Even Google C++ Style guide suggests to initialize local variables at the declaration.

    • Avi Dullu says:

      You read the style guide!! Bravo !

      • Venki says:

        Yeah, I do refer style guide occasionally. It doesn’t explicitly mention to initialize *every* local variable, it emphasizes not to separate declaration and initialization. I would like to mention the below two points,

        1. Initializing every local variable to zero.
        2. Initializing every local variable to non-zero.

        On most processors the first one can be implemented in one or two instructions (on MIPS a dedicated zero-ed register is there, it is just a matter of copying. On other processors, we can XOR a register with itself, and push that value into this variable).

        However, I am concerned with second one. If we initialize a variable to some non zero, say, INT_MAX, the processors needs to fetch this value from program ‘text’ or read only data location, prior to loading the value into actual variable. It may not be economical on few systems. Consider, an embedded system, usually the text section stored on ROM (Flash) which is quite slow compared RAM. And, if we have lots of these initializations, certainly there will be hit on performance. It may not be significant on desktop/server environment. Fortunately, modern day processors do have solutions for this. If they support higher code density (ARM Thumb) they can embed this initialization information as part of instruction itself (ofcourse max size is limited).

        In most cases, whether to initialize or not depends on style (driven by personal taste) and legacy (driven by existing code). All in all, I personally prefer defensive programming. Let the compiler take a call whether to drop off unnecessary intializations (as mentioned above).

        If you get time, I would recommend to read “The Practice of Programming”.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: