日期数组中最长的连续子序列

Question

您好，我有一个 Arraylist 包含递增顺序的日期。日期格式为 yyyy-MM-dd。现在我想找出那个 Arraylist 中最长的连续子序列。我已经在线检查了解决方案，但它们与 int 数组有关，我想找出日期数组。 int 数组的代码：

// Returns length of the longest contiguous subarray
int findLength(int arr[], int n)
{
int max_len = 1;  // Initialize result
for (int i=0; i<n-1; i++)
{
    // Initialize min and max for all subarrays starting with i
    int mn = arr[i], mx = arr[i];

    // Consider all subarrays starting with i and ending with j
    for (int j=i+1; j<n; j++)
    {
        // Update min and max in this subarray if needed
        mn = min(mn, arr[j]);
        mx = max(mx, arr[j]);

        // If current subarray has all contiguous elements
        if ((mx - mn) == j-i)
            max_len = max(max_len, mx-mn+1);
    }
}
return max_len;  // Return result
}

// Utility functions to find minimum and maximum of
// two elements
int min(int x, int y) { return (x < y)? x : y; }
int max(int x, int y) { return (x > y)? x : y; }

Answer 1

我使用这段代码解决了这个问题，如果有人遇到同样的问题，他们可以使用这段代码：

private int getBest(){
    //Getting dates
    ArrayList<Date> successDates = new ArrayList<>();
    SimpleDateFormat sdf = new SimpleDateFormat("yyyy-MM-dd", Locale.getDefault());
    for(int i=0; i<successDays.size(); i++){
        try {
            successDates.add(sdf.parse(successDays.get(i)));
        } catch (ParseException e) {
            e.printStackTrace();
        }
    }
    int max_len = 1;
    for(int i=0; i<successDates.size(); i++){
        Date mn = successDates.get(i);
        Date mx = successDates.get(i);
        for(int j=i+1; j<successDates.size(); j++){
            if(mn.compareTo(successDates.get(j))>0){
                mn = successDates.get(j);
            }
            if(mx.compareTo(successDates.get(j))<0){
                mx = successDates.get(j);
            }
            if(getDaysBetweenDates(mn, mx) == j-i){
                if(max_len < getDaysBetweenDates(mn, mx)+1){
                    max_len = getDaysBetweenDates(mn, mx) + 1;
                }
            }
        }
    }
    return max_len;
}

private int getDaysBetweenDates(Date min, Date max){
    Calendar mn = Calendar.getInstance();
    mn.setTime(min);

    Calendar mx = Calendar.getInstance();
    mx.setTime(max);

    long msDiff = mx.getTimeInMillis() - mn.getTimeInMillis();
    return (int)TimeUnit.MILLISECONDS.toDays(msDiff);
}

Answer 2

tl;博士

ChronoUnit.DAYS.between ( 
    LocalDate.parse( previousString ) , 
    LocalDate.parse( currentString )
)

字符串 != 日期

I have an Arraylist containing dates in increasing order. Dates are of this format yyyy-MM-dd.

这意味着您有 List 个 String 对象，而不是日期。这里的主要挑战是获取日期对象，以便您可以计算它们之间的天数。

java.time

现代方法是使用 java.time classes 取代麻烦的旧遗留 classes（Date、Calendar 等） .

您输入的字符串恰好符合标准 ISO 8601 formats. And the java.time classes happen to use ISO 8601 formats by default when parsing/generating strings. So no need to specify a formatting pattern。

List<String> inputs = new ArrayList<> ();
inputs.add ( "2016-01-23" );
inputs.add ( "2016-01-25" );
inputs.add ( "2016-02-22" ); // End of longest period between dates.
inputs.add ( "2016-02-25" );
inputs.add ( "2016-02-28" );

LocalDate class 表示没有时间和时区的仅日期值。

此示例代码的策略是计算每个 LocalDate（从每个传入的字符串解析）和前一个 LocalDate 之间的天数。如果比目前看到的最长的长，忘记旧的最长的并记住当前循环的数据。

LocalDate longestStart = null;
LocalDate longestStop = null;
LocalDate previousDate = null;
long longestInDays = 0;

ChronoUnit enum 有一些方便的方法，例如计算经过的天数。

for ( String input : inputs ) {
    LocalDate currentDate = LocalDate.parse ( input );
    if ( null == previousDate ) {  // First loop.
        previousDate = currentDate;
        continue;  // Skip the rest of this first loop.
    }
    long currentDays = ChronoUnit.DAYS.between ( previousDate , currentDate );
    if ( currentDays > longestInDays ) {
        // If the current loop exceeds previous longest, remember this one as longest.
        longestInDays = currentDays;
        longestStart = previousDate;
        longestStop = currentDate;
    }
    // Prepare for next loop.
    previousDate = currentDate;
}

将结果转储到控制台。

System.out.println ( "Longest period has days: " + longestInDays + " = " + longestStart + "/" + longestStop );

Longest period has days: 28 = 2016-01-25/2016-02-22

参见 live code in IdeOne.com。

日期数组中最长的连续子序列

Longest consecutive subsequence in dates array

java

android

date

jodatime

tl;博士

字符串 != 日期

java.time