title: in Java, design linear algorithm that finds contiguous subsequence with highest sum
body: <p>this is the question, and yes it is homework, so I don't necessarily want anyone to "do it" for me; I just need suggestions: Maximum sum: Design a linear algorithm that finds a contiguous subsequence of at most M in a sequence of N long integers that has the highest sum among all such subsequences. Implement your algorithm, and confirm that the order of growth of its running time is linear.</p>
  
  <p>I think that the best way to design this program would be to use nested for loops, but because the algorithm must be linear, I cannot do that. So, I decided to approach the problem by making separate for loops (instead of nested ones). </p>
  
  <p>However, I'm really not sure where to start. The values will range from -99 to 99 (as per the range of my random number generating program). </p>
  
  <p>This is what I have so far (not much):</p>
  
  <pre><code>public class MaxSum {
  
  public static void main(String[] args){
      int M = Integer.parseInt(args[0]);
      int N = StdIn.readInt(); 
      long[] a = new long[N]; 
      for (int i = 0; i &lt; N; i++) {
            a[i] = StdIn.readLong();}}}
  </code></pre>
  
  <p>if M were a constant, this wouldn't be so difficult. For example, if M==3:</p>
  
  <pre><code>public class MaxSum2 {
  
      public static void main(String[] args){
          int N = StdIn.readInt(); //read size for array
          long[] a = new long[N]; //create array of size N
          for (int i = 0; i &lt; N; i++) { //go through values of array
                a[i] = StdIn.readLong();} //read in values and assign them to             
                                                  //array indices
  
          long p = a[0] + a[1] + a[2]; //start off with first 3 indices
  
          for (int i =0; i&lt;N-4; i++)
          {if ((a[i]+a[i+1]+a[1+2])&gt;=p) {p=(a[i]+a[i+1]+a[1+2]);}}
                   //if sum of values is greater than p, p becomes that sum
  
          for (int i =0; i&lt;N-4; i++) //prints the subsequence that equals p
          {if ((a[i]+a[i+1]+a[1+2])==p) {StdOut.println((a[i]+a[i+1]+a[1+2]));}}}}
  </code></pre>
  
  <p>If I must, I think MaxSum2 will be acceptable for my lab report (sadly, they don't expect much). However, I'd really like to  make a general program, one that takes into consideration the possibility that, say, there could be only one positive value for the array, meaning that adding the others to it would only reduce it's value; Or if M were to equal 5, but the highest sum is a subsequence of the length 3, then I would want it to print that smaller subsequence that has the actual maximum sum. </p>
  
  <p>I also think as a novice programmer, this is something I Should learn to do. Oh and although it will probably be acceptable, I don't think I'm supposed to use stacks or queues because we haven't actually covered that in class yet. </p>