title: Different Summands problem greedy alogrithm
body: <p>I try to solve Different Summands problem with greedy algorithm </p>
  
  <p><strong>Problem Description</strong></p>
  
  <p><strong>Task</strong>. The goal of this problem is to represent a given positive integer  as a sum of as many pairwise
  distinct positive integers as possible. That is, to find the maximum <code></code> such that <code></code> can be written as
  <code>1 + 2 + · · · + </code> where <code>1, . . . , </code> are positive integers and <code> ̸= </code> for all <code>1 ≤  &lt;  ≤ .</code></p>
  
  <p><strong>Input Format.</strong> The input consists of a single integer .
  Constraints. <code>1 ≤  ≤ 10^9</code>.</p>
  
  <p><strong>Output Format.</strong> In the first line, output the maximum number <code></code> such that <code></code> can be represented as a sum
  of <code></code> pairwise distinct positive integers. In the second line, output <code></code> pairwise distinct positive integers
  that sum up to <code></code> (if there are many such representations, output any of them).</p>
  
  <p><strong>My Code:</strong> </p>
  
  <pre><code>public class DifferentSummands {
      private static List&lt;Integer&gt; optimalSummands(int n) {
          List&lt;Integer&gt; summands = new ArrayList&lt;Integer&gt;();
          int start = 1;
          int newNumber = n;
  
          if (n == 2) {
              summands.add(2);
              return summands;
          }
  
          while (true) {
              if (summands.contains(newNumber - start)) {
                  start++;
                  continue;
              } else {
                  newNumber -= start;
                  summands.add(start);
                  start++;
              }
  
              if (newNumber == 0) {
                  return summands;
              }
          }
      }
  
      public static void main(String[] args) {
          Scanner scanner = new Scanner(System.in);
          int n = scanner.nextInt();
          List&lt;Integer&gt; summands = optimalSummands(n);
          System.out.println(summands.size());
  
          for (Integer summand : summands) {
              System.out.print(summand + " ");
          }
      }
  }
  </code></pre>
  
  <p>My code fails if the input was so big it takes about 3.24 seconds and the max time available is 1.5 seconds.</p>