java - 最大连续子序列和与序列

Question

我试图找到数组的最大和并打印产生该最大和的相应序列。我已经能够获得正确的总和，但是当我尝试打印某些测试数组的序列时，我的程序遗漏了其中一个索引。例如，对于数组 [1, -1, 2, 3, -2]，我的程序找到 5 的最大和，但它只打印 1, -1, 2，而不是 1, -1, 2, 3。我知道问题出在我的 for 循环内，并且我的 count 变量没有正确递增，但我不知道如何修复它。

    import java.util.*;

    public class practice
    {
        public static void main(String args[])
        {
            int arr[] = {1, -1, 2, 3, -2};
            int arr2[] = {1, 12, -2, -15, 10};
            int arr3[] = {0, -1, -3, -5, -6};
            int arr4[] = {1, 2, 3, 4, 5};
            int arr5[] = {1, 12, -2, 15, 10};

            subsequence(arr);
            subsequence(arr2);
            subsequence(arr3);
            subsequence(arr4);
            subsequence(arr5);

        }

        public static void subsequence(int[] arr)
        {
            int max = 0;
            int tempMax = 0;
            int count = 0;

            // My problem is in here:
            for (int i = 0; i < arr.length; i++)
            {
                tempMax += arr[i];
                if (max < tempMax)
                {
                    max = tempMax;
                    count++;
                }
            }

            System.out.println("count = " + count);
            System.out.println("Max sum is " + max);
            System.out.print("Sequence is: ");

            for (int j = 0; j < count; j++)
                System.out.print(arr[j] + " ");

            System.out.println("\n");
        }
    }

这是我的输出

    count = 3
    Max sum is 5
    Sequence is: 1 -1 2 

    count = 2
    Max sum is 13
    Sequence is: 1 12 

    count = 0
    Max sum is 0
    Sequence is: 

    count = 5
    Max sum is 15
    Sequence is: 1 2 3 4 5 

    count = 4
    Max sum is 36
    Sequence is: 1 12 -2 15 

这是我编辑的代码:

public class practice
{
    public static void main(String args[])
    {
        int arr[] = {1, -1, 2, 3, -2};
        int arr2[] = {1, 12, -2, -15, 10};
        int arr3[] = {0, -1, -3, -5, -6};
        int arr4[] = {-1, 2, 3, -4, -5};
        int arr5[] = {1, 12, -2, 15, 10};

        subsequence(arr);

        subsequence(arr2);

        subsequence(arr3);

        subsequence(arr4);

        subsequence(arr5);
    }

    public static void subsequence(int[] arr)
    {
        int max = 0;
        int tempMax = 0;
        int count = 0;
        int start = 0;
        int end = 0;

        if (arr[0] < 0)
           start++;


        for (int i = start; i < arr.length; i++)
        {
            tempMax += arr[i];

            if (max < tempMax)
            {
                max = tempMax;
                count = i;
            }

            if (Math.abs(arr[i]) < tempMax)
               end = i;


         }

         System.out.println("count = " + count);
         System.out.println("Max sum is " + max);
         System.out.print("Sequence is: ");

         if (arr[end] < 0)
               end--;

         for (int j = start; j <= end; j++)
             System.out.print(arr[j] + " ");

         System.out.println("\n");
         }

    }

这是我的新输出:

count = 3
Max sum is 5
Sequence is: 1 -1 2 3 

count = 1
Max sum is 13
Sequence is: 1 12 

count = 0
Max sum is 0
Sequence is: 0 

count = 2
Max sum is 5
Sequence is: 2 3 

count = 4
Max sum is 36
Sequence is: 1 12 -2 15 10 

Answer 1

您的count变量没有意义，因为只有在找到最大值的新候选者时才增加它。当您找到新的最大候选时，将 count 设置为当前索引:

count = i;

然后，当您打印序列时，将条件更改为 j <= count .

顺便说一句，我不确定您的实现是否正确。您始终返回一个从数组开头开始的子序列。如果具有最大和的子序列不是从头开始怎么办？ (例如，在[-1,2,3,4,5]中，最大序列为[2,3,4,5])。